サイズnの配列、1要素n/2回

Question

n個の整数の配列が与えられ、1つの要素がn/2回以上出現するとします。その要素を線形時間と一定の余分な空間で見つける必要があります。

YAAQ：さらに別の配列の質問です。

Answer 1

私はそれが（C＃の場合）の線に沿って何かでひそかな疑いを持っている

// We don't need an array 
public int FindMostFrequentElement(IEnumerable<int> sequence) 
{ 
    // Initial value is irrelevant if sequence is non-empty, 
    // but keeps compiler happy. 
    int best = 0; 
    int count = 0; 

    foreach (int element in sequence) 
    { 
     if (count == 0) 
     { 
      best = element; 
      count = 1; 
     } 
     else 
     { 
      // Vote current choice up or down 
      count += (best == element) ? 1 : -1; 
     } 
    } 
    return best; 
} 

これは動作しそうに聞こえるが、それはありません。 （Proof as a postscript file、Boyer/Mooreの礼儀）

Answer 2

私が最初に考えた（十分ではありませんが）に次のようになります。

• ソート代わりに配列
• 戻る途中要素

しかし、それはO（n個のnを記録）になり、どのような再帰的解決法もそうである。

アレイを破壊的に変更できる場合（およびその他のさまざまな条件が適用されます）、要素をカウントなどで置き換えるパスを実行できます。あなたは配列について何か知っていますか？それを変更することは許されていますか？

編集私の答えは後世に残していますが、Skeetはそれを得たと思います。

Answer 3

について： ランダムにK要素の小さなサブセットを選択し、重複を探します（最初の4、最初の8など）。 K == 4の場合、重複のうち少なくとも2つを取得しない確率は1/8です。 K == 8の場合、1％未満になります。重複が見つからない場合は、処理を繰り返すまでプロセスを繰り返します。 （他の要素がより無作為に分布していると仮定すると、例えば、配列の "49％=" A "、配列の51％=" B "）、これは非常にうまく機能しません。

例えば：

findDuplicateCandidate: 
    select a fixed size subset. 
    return the most common element in that subset 
    if there is no element with more than 1 occurrence repeat. 
    if there is more than 1 element with more than 1 occurrence call findDuplicate and choose the element the 2 calls have in common  

これは一定の順序動作であるので、次に確認するために（N）、アレイの線形走査を行う（データセットが悪いわけではない場合）。

Answer 4

説明したように、インプレース基数ソートを行うことができます。here[pdf]これは余分なスペースと線形時間を必要としません。連続した要素を数え、count> n/2で終わる単一のパスを作ることができます。

Answer 5

int findLeader(int n, int* x){ 
    int leader = x[0], c = 1, i; 
    for(i=1; i<n; i++){ 
     if(c == 0){ 
      leader = x[i]; 
      c = 1; 
     } else { 
      if(x[i] == leader) c++; 
      else c--; 
     } 
    } 

    if(c == 0) return NULL; 
    else { 
     c = 0; 
     for(i=0; i<n; i++){ 
      if(x[i] == leader) c++; 
     } 
     if(c > n/2) return leader; 
     else return NULL; 
    } 
} 

私はこのコードを作成したわけではありませんが、これは問題のために機能します。最初の部分は潜在的なリーダーを探し、2番目の部分は配列にn/2回以上出現するかどうかを調べます。

Answer 6

中央値を求めると、ソートされていない配列ではO（n）が必要です。 n/2以上の要素は同じ値に等しいので、中央値もその値に等しい。

Answer 7

これは私が最初に考えたものです。

私は不変の "1つの要素が2回以上出現する"ようにしましたが、問題を減らしました。

[i]、a [i + 1]の比較を開始できます。それらが等しい場合、a [i + i]、a [i + 2]を比較します。そうでなければ、配列からa [i]、a [i + 1]の両方を取り除く。i> =（現在のサイズ）/ 2になるまでこれを繰り返します。この時点で、最初の（現在のサイズ）/ 2の位置を占める 'THE'要素があります。 これにより、不変量が維持されます。

唯一の注意点は、[それは（n）の複雑さをOを与えるため。]我々は、配列が、リンクされたリストであることを前提としていることである

人々は何と言いますか？ PHPで

-bhupi

Answer 8

--- plsはそれが正しい

function arrLeader($A){ 
$len = count($A); 
$B = array(); 
$val=-1; 
$counts = array_count_values(array); //return array with elements as keys and occurrences of each element as values 
for($i=0;$i<$len;$i++){ 
    $val = $A[$i]; 
    if(in_array($val,$B,true)){//to avoid looping again and again 
    }else{ 
    if($counts[$val]>$len/2){ 
     return $val; 
    } 
    array_push($B, $val);//to avoid looping again and again 
    } 
} 
return -1; 
} 

Answer 9

int n = A.Length; 
      int[] L = new int[n + 1]; 
      L[0] = -1; 
      for (int i = 0; i < n; i++) 
      { 
       L[i + 1] = A[i]; 
      } 
      int count = 0; 
      int pos = (n + 1)/2; 
      int candidate = L[pos]; 
      for (int i = 1; i <= n; i++) 
      { 
       if (L[i] == candidate && L[pos++] == candidate) 
        return candidate; 
      } 
      if (count > pos) 
       return candidate; 
      return (-1);