2

私は数字のセットを持っています: 1 1 2 8 5 6 6 7 8 8 4 2...

上記の数値のサブ配列（指定されたサイズのk）で重複要素を検出したい...例：k = 3`の増加するサブ配列を考えてみましょう

Sub array 1 :{1,1,2}
Sub array 2 :{1,2,8}
Sub array 3 :{2,8,5}
Sub array 4 :{8,5,6}
Sub array 5 :{5,6,6}
Sub array 6 :{6,6,7}
....

したがって、私のアルゴリズムは、サブ配列1、5、および6に重複が含まれていることを検出する必要があります..私のアプローチ：

1)最初のk要素を一時配列(ベクトル)にコピーします

2) C++ STL で #include ファイルを使用する...unique() を使用して、ベクトルのサイズに変更があるかどうかを判断します..

この問題に対処する方法の他の手がかり....指定された番号のリストが大きい場合、私の方法は多くの時間とスペースを消費するため..

4

1 に答える 1

0

O(n)平均的な時間とO(k)空間の解決策は、ハッシュベースのヒストグラムを作成し、各サブリストの要素の#occurancesを維持しながら配列を反復することです。
各反復で、（ヒストグラムの関連する入口を減らすことによって）最も古い要素を追い出し、新しい要素を追加します。
また、numDupes現在持っている重複の数をカウントし、現在の候補から要素を追加/削除するときに維持される変数を維持します。

擬似コード（1つのエラーか何かでオフになっている場合は申し訳ありませんが、これはアイデアです）：

numDupes = 0
histogram = new map<int,int>;
//first set:
for each i form 0 to k:
  if histogram.contains(arr[i]):
     histogram.put(arr[i],histogram.get(arr[i]) + 1)
     numDupes += 1
  else:
     histogram.put(arr[i],1)
//each iteration is for a new set
if (numDupes > 0) print 1 //first sub array has dupes
for each i from k to n:
   if (histogram.get(arr[i-k]) > 1) numDupes -= 1 //we just removed a dupe
   histogram.put(arr[i-k],histogram.get(arr[i-k] - 1)) //take off "eldest" element.
   if (histogram.contains(arr[i]) && histogram.get(arr[i]) > 0):
       histogram.put(arr[i],histogram,get(arr[i]) + 1))
       numDupes += 1 //we just added a dupe
   else:
       histogram.put(arr[i],1)
   if (numDupes > 0) print i-k+1 // the current sub array contains a dupe

最初の答えには小さな間違いがありました。最後に追加された要素が重複を引き起こさなかった場合にケースをキャッチできませんでしたが、まだ1つあります（例のサブ配列6のように）。
これは、検出された現在の重複の数をカウントする追加の整数を維持し、カウンターが0より大きい場合にサブ配列を出力することで解決できます（疑似コードを更新）。

注：O(k)スペースを確保histogramするには、値が0のときに要素を削除する必要があります。

于 2012-10-14T14:49:59.153 に答える