要素の繰り返し数を見つけるためのより良いアルゴリズム。時間の

Question

私は与えられた要素のバイナリ検索を試みて、それよりも大きいか小さい要素を得るまで左と右にそれを横断しましたが、すべての要素が同じならO（n）時間の複雑さまで進みます。どんなに良いアルゴもありますか？

Answer 1

範囲の下限（および/または上限）を検出し、下限、および範囲の要素の上限または下限のいずれかをバイナリ検索するバイナリ検索を使用できますあなたが気にするものより1つ大きい

編集：私が下限を見つけるために見たコードのほとんどは、実際に必要なものよりも少し複雑です（私は信じています）。中央の要素が求め要素に等しい場合は、左半分を選択する最初の検索では

：

int *find(int *left, int *right, int val) { 
    assert(left<right); 
    while (left < right) { 
     int *middle = left + (right - left)/2; 
     if (*middle < val) 
      left = middle + 1; 
     else 
      right = middle; 
    } 
    return left; 
} 

Answer 2

は、2件のバイナリ検索を行います。

中間の要素が検索される要素と等しい場合は、右の半分を選択します。 Javaで

サンプルコード：

class Test { 

    public static int findElem(int[] arr, int elem, int l, int h,boolean first) { 
     if (h - l <= 1) 
      return first ? (arr[l] == elem ? l : h) : (arr[h] == elem ? h : l); 

     int m = l + (h - l)/2; 

     if (arr[m] < elem || (arr[m] == elem && !first)) 
      return findElem(arr, elem, m, h, first); 

     return findElem(arr, elem, l, m, first); 
    } 

    public static int findElem(int[] arr, int elem, boolean first) { 
     return findElem(arr, elem, 0, arr.length, first); 
    } 

    public static void main(String[] args) { 
     int[] arr = { 0, 1, 2, 2, 2, 3, 3, 4, 4, 5 }; 

     int elem = 2; 

     System.out.println("First index: " + findElem(arr, elem, true)); 
     System.out.println("Last index : " + findElem(arr, elem, false)); 
    } 
} 

Answer 3

あなたがすべき最初に、あなたのマッチングシーケンスの最後の要素のためのバイナリ検索。 C++を使用している場合は、STLにlower_boundとupper_boundのような機能があります。それ以外の場合は、アルゴリズムの単純な変更です。

また、あなたは3件のバイナリ検索し使用することができます：

バイナリ検索あなたの範囲の左側のためにあなたの値と一致するすべての要素について

1. バイナリ検索を
の右側のため
2. バイナリ検索範囲

ただし、最後の2を実行できるということは、最初の解決策を達成したことを意味します（下限/上限を見つけることによって）

Answer 4

これを複数回実行する場合は、要素値をキーとして、最初と最後の要素のインデックスを値としてハッシュテーブルを作成できます。

ハッシュテーブルを作成するためにデータを読み取る操作はO（n）ですが、インデックスを参照する操作はO（1）操作に近いものです。

Answer 5

並べ替えられた配列aがnタイプのTであるとします。次のように特定の要素にxあなたはそれの繰り返しの数を見つけることができます：

T* ub = upper_bound(a, a + n, x); 
int answer = ub - lower_bound(a, ub, x); 

複雑さが明らかにO(logn)です。すべての要素が同じであるか、またはxがaにある場合、upper_boundはa+nに戻り、lower_boundは完全な間隔で動作し、これらの最悪のケースでは2 * lognの反復を行います。