0

给定一个数组：

array = [16 16 16 22 23 23 23 25 52 52 52]

我想返回一个指向三个重复数字元素的索引列表。在这种情况下，这将是：

indices = find_sequence(nbr_repeats = 3)
print indices
 [0 1 2  4 5 6  8 9 10]

为了实现而使用的最快和最优雅的算法是find_sequence什么？

4

4 回答 4

2

我所知道的最简单的方法……记录你第一次看到数字的地方。继续直到你找到一个不同的数字，然后如果序列足够长，将所有数字从序列的开头添加到结尾之前。

（当然，在检查完元素后，您还必须检查序列长度。我通过迭代一个结束并在最后一次迭代中跳过元素检查来做到这一点。）

To find_repeats (input : list, minimum : integer):
    start := 0
    result := []
    for each x from 0 to (input length):
        ' "*or*" here is a short-circuit or
        ' so we don't go checking an element that doesn't exist
        if x == (input length) *or* array[x] != array[start]:
            if (x - start) >= minimum:
                append [start...(x - 1)] to result
            start := x
    return result
于 2012-06-12T23:11:19.740 回答
1

基于OP的假设：

  1. 列表已排序
  2. 最大频率是nbr_repeats

这可能有效：

def find_sequence(nbr_repeats, l):
    res = []
    current = -1
    count = 0
    idx = 0
    for i in l:
        if i == current:
            count += 1
            if count == nbr_repeats:
                for k in reversed(range(nbr_repeats)):
                    res.append(idx-k)
        else:
            current = i
            count = 1
        idx += 1
    return res
于 2012-06-12T23:07:20.320 回答
1

这在我看来像是Boyer-Moore 字符串搜索算法的一个特例，并且由于您使用的任何语言都将包含字符串搜索的优化，也许最优雅的答案是将您的数据视为字符数组（即字符串）和使用您的语言的内置字符串搜索功能...请注意，这仅适用于您的数字适合您的语言支持的字符集（例如，ASCII 中没有大于 128 的数字）

于 2012-06-13T00:17:44.840 回答
0

由于您没有指定语言，因此这是一个伪代码：

find_sequence(array: array of int, nbr_repeats: int) : array of int
  retVal = emty array of int // the return'd array
  last = empty array of int  // collection of last seen same elements
  i = -1
  for each element e in array
    ++i
    if (isempty(last))
      add(last, e)   // just starting
    else if (count(last, e) >= nbr_repeats)
      add(retVal, i-nbr_repeats) // found an index
    else if (e == first(last))
      add(last, e)   // we have encountered this element before
    else
      if (count(last, e) >= nbr_repeats)
        for (j=nbr_repeats-1; j>0; --j)
          add(retVal, i-j) // catching up to i with indices
      last = [e]     // new element

    if (count(last, e) >= nbr_repeats)
      for (j=nbr_repeats-1; j>0; --j)
        add(retVal, i-j) // handle end of array properly

  return retVal

编辑：删除了关于排序的评论，因为它会破坏原始索引。

注意：您也可以只保留最后一个元素及其所见计数，而不是维护最后一个相同元素的列表

于 2012-06-12T22:41:29.083 回答