特定の数値が配列の半分以上を占めるかどうかを調べるためのn log（n）ランタイムを持つ解とは何か

Question

プログラムの要件は、n/2回にわたって発生する数値を配列に出力することです。解のアルゴリズムの実行時間がn log（n）であることを確認します。

[2、1、3、2] = Noの結果 [1、5 2、5、5] = 5

私の現在のソリューションない：これに関しては

int answer = -1; 
    int[] a = {2, 4, 2, 5, 1}; 
    int[] occurances = {0, 0, 0, 0, 0, 0}; 

    for(int i = 0; i < a.length; i++){ 
     occurances[a[i]]++; 
    } 

    for(int i = 0; i < occurances.length; i++){ 
     if(occurances[i] > ((double)a.length)/2){ 
      answer = i; 
     } 
    } 

    System.out.println(answer); 

、私のソリューションの実行時間は何ですか？私はそれが一度だけ配列を通過するので、それがn log（n）だとは思わない。

n log（n）でない場合、n log（n）を持つ解は何ですか？ もしそうなら、それはなぜn長（n）ですか？

Answer 1

解は配列の最大値に依存するので、疑似多項式、つまりO（n + MAX）です。MAXは配列の中で最も高い値です。

• ソート配列
• 値は、複数のアレイの半分以上を占めている場合、それは次のとおりです。より多くのあなたがこのアルゴリズムに従うことができ、アレイの半分以上を占めている価値があるかどうかを確認するために

  ソートされた配列の中央のセルを占有しようとします（Pigeonhole principle参照）。下のステップで使用する

• 中間要素を含む範囲の下位インデックスと上位インデックスを検索する
• 中間要素の上位インデックスと下位インデックスの差を比較する配列の長さの半分まで
• インデックスの差が長さの半分を超える場合、中央の要素は半分以上の時間に含まれます。それ以外の場合、答えは「いいえ」です。

別の方法としては、ハッシュテーブルでカウントを使用することです：

• 要素に要素をマップするハッシュテーブルを構築Oでカウント（N）
• ハッシュテーブルを歩き、そして取ります