3

その配列のすべての一意の要素が存在する整数配列の最小間隔を見つけるにはどうすればよいですか。たとえば、私の配列は次のとおりです。1 1 1 2 3 1 1 4 3 3 3 2 1 2 2 4 1 最小間隔はインデックス 3 からインデックス 7 です。O(nlogn) 以下のアルゴリズムを探しています (n< =100000)

4

1 に答える 1

6

戦略は、最後から最初まで繰り返し、各整数を最後に見たのはいつかを思い出します。例えば。真ん中のどこかで、最後にインデックス15で1、インデックス20で2、インデックス17で3を見ました。間隔の長さは、最後に見た最大インデックスから現在のインデックスを引いたものです。

最大インデックスを簡単に見つけるには、自己平衡二分探索木（BST）を使用する必要があります。これは、O(log n)挿入と削除の時間があり、最大のインデックスのルックアップ時間が一定であるためです。

たとえば、最後に1を表示したインデックスを更新する必要がある場合は、現在の最後に表示されたインデックス（15）を削除し、最後に表示された新しいインデックスを挿入します。

各整数型で許可されているすべての終了インデックスで自己平衡BSTを更新することにより、最大のものを選択して、そこで終了できると言うことができます。

正確なコードは、入力がどのように定義されているかによって異なります（たとえば、すべての整数が何であるかを知っているかどうか、つまり、配列に1から4までのすべての整数が存在することがわかっている場合は、コードが簡略化されます）。

反復はO(n)、BSTはO(log n)です。全体的にですO(n log n)。

実装の詳細

これの実装には少し手間がかかります。

初期化：

  • 各開始インデックスの間隔の長さ。
  • 特定の整数を最後に見たときの配列。（通常の配列を使用する代わりに、配列に含まれる可能性のある整数がわからない場合は、連想配列を使用してください（map<>C ++など））。
  • 優先キューのようなタイプのヒープ。キューの先頭がその中の最大整数です。あなたはそれからものを簡単に取り除くことができる必要があるので、自己平衡二分探索木を使用してください

ループ内（入力配列の終わりから入力配列の始まりまでのループインデックス）、

  • この特定のインデックスについて、最後に表示された配列を更新できます。

    表示される整数を確認し、最後に表示された配列のインデックスのエントリを更新するだけです。

  • 最後に表示された配列の前後を使用して、BSTを更新します（古い終了インデックスを削除し、新しいインデックスを追加します）

  • 必要な最大の終了インデックス（BSTから）に基づいて、この開始インデックスの間隔の長さを更新します。

  • これまでに見たことのない整数が表示された場合は、このインデックスより上のインデックスを開始するためにすべての間隔の長さを無効にします（または、すべての整数が少なくとも1回表示されるまで間隔の長さを更新しないでください）。

C++コードの実装

  • すべての整数0〜（k-1）が入力配列にあると仮定します
  • 免責事項：テストされていません
  • 無視し#includeてmain機能する

コード：

int n=10,k=3;
int input[n]=?;
unsigned int interval[n];
for (int i=0;i<n;i++) interval[i]=-1; // initialize interval to very large number
int lastseen[k];
for (int i=0;i<k;i++) lastseen[i]=-1; // initialize lastseen
multiset<int> pq;

for (int i=n-1;i>=0;i--) {
  if (lastseen[input[i]] != -1) // if lastseen[] already has index
    pq.erase(pq.find(lastseen[input[i]])); // erase single copy
  lastseen[input[i]]=i; // update last seen
  pq.insert(i); // put last seen index into BST
  if (pq.size()==k) { // if all integers seen (nothing missing)
    // get (maximum of endindex requirements) - current index
    interval[i] = (*pq.rbegin())-i+1;
  }
}
// find best answer
unsigned int minlength=-1;
int startindex;
for (int i=0;i<n;i++) {
  if (minlength>interval[i]) { // better answer?
    minlength=interval[i];
    startindex=i;
  }
}
// Your answer is [startindex,startindex+minlength)
于 2012-09-03T05:32:20.227 に答える