0

与えられた配列:

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

3 つの繰り返し数の要素を指すインデックスのリストを返したい。この場合、次のようになります。

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

これは、ボイヤームーア文字列検索アルゴリズムの特殊なケースのように見えます。使用する言語には文字列検索の最適化が含まれるため、おそらく最もエレガントな答えは、データを文字配列（つまり文字列）として扱い、言語に組み込まれている文字列検索機能を使用してください...これは、数値が言語でサポートされている文字セットに適合する場合にのみ機能することに注意してください（たとえば、ASCIIで128より大きい数値は使用しないでください）。

于 2012-06-13T00:17:44.840 に答える
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 に答える
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 に答える