40

質問があり、何度も考え直そうとしましたが、何も得られなかったので、ここに質問を投稿しました。多分私はそれを機能させるために、他の人の視点を得ることができます...

問題は、奇数回発生する 1 つを除いて、偶数回発生する値のコレクションで構成される SORTED 配列が与えられることです。log n 時間で解を見つける必要があります。

O(n) 時間で解を見つけるのは簡単ですが、log n 時間で実行するのはかなり難しいようです。

4

15 に答える 15

30

定理:この問題のすべての決定論的アルゴリズムは、最悪の場合にΩ(log 2 n)のメモリ位置を調べます。

証明(より形式的なスタイルで完全に書き直したもの):

k > 0 を奇数とし、n = k 2とします。(log 2 (k + 1)) 2 = Ω(log 2 n) プローブを強制する敵について説明します。

同一要素の最大部分列をグループと呼びます。敵対者の可能な入力は、長さ k の k 個のセグメントx 1 x 2 … x kで構成されます。各セグメント x jに対して、整数 b j ∈ [0, k] が存在し、x jは j - 1 の b jコピーとそれに続く j の k - b jコピーで構成されます。各グループは最大 2 つのセグメントに重なり、各セグメントは最大 2 つのグループに重なります。

Group boundaries
|   |     |   |   |
 0 0 1 1 1 2 2 3 3
|     |     |     |
Segment boundaries

2 の増加がある場合は常に、慣例により二重境界を想定します。

Group boundaries
|     ||       |   |
 0 0 0  2 2 2 2 3 3

Claim : j番目のグループ境界 (1 ≤ j ≤ k) の位置は、セグメント x jによって一意に決定されます。

証明: ((j - 1) k + b j )番目のメモリ位置の直後であり、x jは b jを一意に決定します。///

x jのプローブの結果が x jを一意に決定する場合、アルゴリズムはj番目のグループ境界を観察したと言います。慣例により、入力の開始と終了は常に観察されます。アルゴリズムがグループ境界の位置を監視せずに一意に決定する可能性があります。

Group boundaries
|   X   |   |     |
 0 0 ? 1 2 2 3 3 3
|     |     |     |
Segment boundaries

0 0 ? だけが与えられた場合、アルゴリズムは? は 0 または 1 です。ただし、コンテキストでは、? そうしないと 3 つの奇数グループが存在し、X でのグループ境界が推測できるため、1 でなければなりません。これらの推論は敵対者にとって問題になる可能性がありますが、問題のグループ境界が「無関係」になった後にのみ行うことができることが判明しました。

Claim :アルゴリズムの実行中の任意の時点で、アルゴリズムが観察したグループ境界のセットを考慮します。ちょうど 1 つの連続したペアが奇数の距離にあり、奇数グループはそれらの間にあります。

証明: 連続する 1 つおきのペアは、偶数グループのみをバインドします。///

特別な連続したペアで区切られた奇数長のサブシーケンスを関連するサブシーケンスと定義します。

主張:関連する部分列の内部のグループ境界は一意に決定されません。そのような境界が少なくとも 1 つある場合、奇数グループの ID は一意に決定されません。

証明: 一般性を失うことなく、関連するサブシーケンスに含まれていない各メモリ位置がプローブされ、関連するサブシーケンスに含まれる各セグメントにはプローブされていない位置が 1 つだけあると仮定します。j番目のグループ境界 (B と呼ぶ) が関連するサブシーケンスの内部にあるとします。仮説により、x jへのプローブは、最大 2 つの連続した可能性まで B の位置を決定します。左の観測境界から奇数の距離にあるものを奇左と呼び、もう一方を奇右と呼びます. 両方の可能性について、左から右に作業し、残りのすべての内部グループ境界の位置を修正して、その左側のグループが均等になるようにします。(それぞれに 2 つの連続する可能性があるため、これを行うことができます。) B が奇数左にある場合、その左のグループは一意の奇数グループです。B が奇数右にある場合、関連するサブシーケンスの最後のグループは一意の奇数グループです。どちらも有効な入力であるため、アルゴリズムは B の位置も奇数グループも一意に決定していません。///

例：

Observed group boundaries; relevant subsequence marked by […]
[             ]   |
 0 0 Y 1 1 Z 2 3 3
|     |     |     |
Segment boundaries

Possibility #1: Y=0, Z=2
Possibility #2: Y=1, Z=2
Possibility #3: Y=1, Z=1

この主張の結果として、アルゴリズムは、それがどのように機能するかに関係なく、関連するサブシーケンスを 1 つのグループに絞り込む必要があります。したがって、定義上、いくつかのグループ境界を観察する必要があります。敵対者は、可能な限り多くの可能性をオープンにしておくという単純なタスクを負っています。

アルゴリズムの実行中の任意の時点で、敵対者は、関連するサブシーケンスの外側の各メモリ位置に対して 1 つの可能性を内部的にコミットします。最初は、関連するサブシーケンスは入力全体であるため、初期コミットメントはありません。アルゴリズムが x jのコミットされていない場所をプローブするときはいつでも、攻撃者は 2 つの値のいずれかにコミットする必要があります: j - 1 または j。j番目の境界が観測されないようにすることができる場合、(観測に関して) 残りの可能性の少なくとも半分を残す値を選択します。それ以外の場合は、グループの少なくとも半分を関連する間隔に保持するように選択し、残りの値をコミットします。

このようにして、攻撃者はアルゴリズムに少なくとも log 2 (k + 1) 個のグループ境界を観察するように強制し、j番目のグループ境界を観察する際に、アルゴリズムは少なくとも log 2 (k + 1) 個のプローブを作成するように強制されます。

拡張子:

この結果は、入力をランダム化し、(アルゴリズムの観点から) "せいぜい半分" を "せいぜい半分の期待値" に置き換え、標準的な濃度不等式を適用することにより、ランダム化されたアルゴリズムに直接拡張されます。

また、グループが s 個のコピーよりも大きくならない場合にも適用されます。この場合、下限はΩ(log n log s)です。

于 2010-07-05T21:46:32.670 に答える
15

ソートされた配列は、二分探索を示唆しています。平等と比較を再定義する必要があります。等式単純とは、要素の数が奇数であることを意味します。グループの最初または最後の要素のインデックスを観察することで、比較を行うことができます。最初の要素は、奇数グループの前に偶数インデックス (0 ベース) になり、奇数グループの後に奇数インデックスになります。二分探索を使用して、グループの最初と最後の要素を見つけることができます。総コストは O((log N)²) です。

O((log N)²) の証明

  T(2) = 1 //to make the summation nice
  T(N) = log(N) + T(N/2) //log(N) is finding the first/last elements

一部の N=2^k については、

T(2^k) = (log 2^k) + T(2^(k-1))
       = (log 2^k) + (log 2^(k-1)) + T(2^(k-2))
       = (log 2^k) + (log 2^(k-1)) + (log 2^(k-2)) + ... + (log 2^2) + 1
       = k + (k-1) + (k-2) + ... + 1
       = k(k+1)/2
       = (k² + k)/2
       = (log(N)² + log(N))/ 2
       = O(log(N)²)
于 2010-07-05T16:53:32.447 に答える
11

配列の中央の要素を見てください。いくつかの適切なバイナリ検索を使用すると、配列内の最初と最後の出現を見つけることができます。iたとえば、中央の要素が「a」の場合、次のようにandを見つける必要がありjます。

[* * * * a a a a * * *]
         ^     ^ 
         |     |
         |     |
         i     j

j - i偶数ですか？これで完了です。それ以外の場合 (これがここでの鍵です)、尋ねる質問は i が偶数か奇数か? この知識が何を意味するか分かりますか？あとは簡単です。

于 2010-07-05T17:04:41.587 に答える
6

この回答は、「throwawayacct」によって投稿された回答をサポートしています。彼は賞金に値する。私はこの質問に時間を費やしましたが、奇数回発生する数を見つけるには Ω(log(n)^2) クエリが必要であるという彼の証明が正しいと確信しています。彼の解決策をざっと読んだだけで、まったく同じ議論を再現することになったので、私は確信しています。

このソリューションでは、敵対者が入力を作成して、アルゴリズムの処理を困難にしますが、人間のアナライザーの処理も単純にします。入力は、それぞれが k エントリを持つ k ページで構成されます。エントリの総数は n = k^2 であり、O(log(k)) = O(log(n)) および Ω(log(k)) = Ω(log(n)) であることが重要です。入力を行うために、敵対者は 00...011...1 の形式の長さ k の文字列を作成し、任意の位置に遷移します。次に、文字列内の各記号は、aa...abb...b の形式の長さ k のページに展開されます。ここで、i 番目のページでは、a=i および b=i+1 です。各ページの遷移も任意の位置にありますが、パリティがページの展開元のシンボルと一致する場合を除きます。

アルゴリズムの最悪のケースを分析する「敵対的な方法」を理解することが重要です。敵対者は、アルゴリズムの入力に関するクエリに回答しますが、将来の回答にコミットすることはありません。答えは一貫している必要があり、アルゴリズムが結論に達するのに十分なほど敵が固定されたときに、ゲームは終了します。

その背景を踏まえて、次のような観察結果があります。

1）そのページでクエリを作成してページ内の遷移のパリティを学習したい場合は、遷移の正確な位置を学習する必要があり、Ω（log（k））クエリが必要です。クエリのコレクションは遷移点を間隔に制限し、1 を超える長さの間隔には両方のパリティがあります。そのページのトランジションの最も効率的な検索は、二分検索です。

2)最も微妙で最も重要な点:特定のページ内のトランジションのパリティを判断するには 2 つの方法があります。そのページで遷移を見つけるのに十分なクエリを作成するか、前のページと後のページの両方で同じパリティが見つかった場合にパリティを推測できます。この二者択一から逃れることはできません。一連のクエリは、各ページの遷移ポイントを一定の間隔に制限します。パリティに対する唯一の制限は、長さ 1 の間隔から生じます。それ以外の場合、遷移点は一貫したパリティを持つために自由に小刻みに動きます。

3) 敵対的方法では、ラッキーストライクはありません。たとえば、あるページの最初のクエリが、中央ではなく端に向かっているとします。敵対者は答えを約束していないので、自由に移行を長期化することができます。

4) 最終結果は、Ω(log(k)) ページのパリティを直接調べることを余儀なくされ、これらのサブ問題のそれぞれに対する作業も Ω(log(k)) になります。

5) 物事は、敵対的な選択よりもランダムな選択の方がはるかに優れているわけではありません。数学はより複雑です。なぜなら、厳密に「はい」はパリティを知っているか、「いいえ」はパリティを知らないかではなく、部分的な統計情報を取得できるからです。しかし、ほとんど違いはありません。たとえば、各ページの長さ k^2 を指定すると、各ページの最初の log(k) クエリでは、そのページのパリティについてほとんど何もわからない可能性が高くなります。敵対者は最初にランダムな選択を行うことができ、それでも機能します。

于 2010-07-12T16:40:54.920 に答える
5

配列の中央から開始し、中央の値とは異なる値になるまで後方に移動します。その境界の上の数値が奇数または偶数のインデックスにあるかどうかを確認します。奇数の場合は、奇数回出現する数が左にあるので、最初と見つかった境界の間で検索を繰り返します。偶数の場合、奇数回出現する数は配列の後半にある必要があるため、右半分で検索を繰り返します。

前述のように、これには対数成分と線形成分の両方があります。全体を対数的に保ちたい場合は、配列を逆方向に別の値に移動するのではなく、代わりに二分探索を使用します。ただし、同じ数字が何度も繰り返されることが予想される場合を除き、二分探索は意味がないかもしれません。

于 2010-07-05T17:02:22.997 に答える
3

log（N / C）* log（K）で機能するアルゴリズムがあります。ここで、Kは最大の同じ値の範囲の長さであり、Cは検索される範囲の長さです。

このアルゴリズムと以前に投稿されたほとんどのアルゴリズムとの主な違いは、すべての同じ値の範囲が短い場合を利用することです。配列全体を二分探索するのではなく、最初に1、2、4、8、...（log（K）反復）ステップでジャンプして大まかな推定値をすばやく見つけ、次に二分探索によって境界を見つけます。結果の範囲（再びlog（K））。

アルゴリズムは次のとおりです（C＃で記述）。

// Finds the start of the range of equal numbers containing the index "index", 
// which is assumed to be inside the array
// 
// Complexity is O(log(K)) with K being the length of range
static int findRangeStart (int[] arr, int index)
{
    int candidate = index;
    int value = arr[index];
    int step = 1;

    // find the boundary for binary search:
    while(candidate>=0 && arr[candidate] == value)
    {
        candidate -= step;
        step *= 2;
    }

    // binary search:
    int a = Math.Max(0,candidate);
    int b = candidate+step/2;
    while(a+1!=b)
    {
        int c = (a+b)/2;
        if(arr[c] == value)
            b = c;
        else
            a = c;
    }
    return b;
}

// Finds the index after the only "odd" range of equal numbers in the array.
// The result should be in the range (start; end]
// The "end" is considered to always be the end of some equal number range.
static int search(int[] arr, int start, int end)
{
    if(arr[start] == arr[end-1])
        return end;

    int middle = (start+end)/2;

    int rangeStart = findRangeStart(arr,middle);

    if((rangeStart & 1) == 0)
        return search(arr, middle, end);
    return search(arr, start, rangeStart);
}

// Finds the index after the only "odd" range of equal numbers in the array
static int search(int[] arr)
{
    return search(arr, 0, arr.Length);
}
于 2010-07-05T19:59:30.573 に答える
2

中央の要素 e を取ります。二分探索を使用して、最初と最後のオカレンスを見つけます。O(log(n)) 奇数の場合は e を返します。それ以外の場合は、要素数が奇数の側に再帰します [....]eeee[....]

ランタイムは log(n) + log(n/2) + log(n/4).... = O(log(n)^2) になります。

于 2010-07-05T22:37:31.773 に答える
1

このアルゴリズムを使用できます。

int GetSpecialOne(int[] array, int length)
{
   int specialOne = array[0];

   for(int i=1; i < length; i++)
   {
      specialOne ^= array[i];
   }
   return specialOne;
}

ここhttp://www.technicalinterviewquestions.netにある同様の質問の助けを借りて解決しました

于 2011-06-21T15:08:00.717 に答える
1

ああ。答えがあります。

バイナリ検索を実行し、各値を検索しながら、同じ値を持つ最初のエントリが見つかるまで後方に移動します。インデックスが偶数の場合、オッドボールの前にあるので、右に移動します。
その配列インデックスが奇数の場合、オッドボールの後なので、左に移動します。

疑似コード (これは一般的な考え方であり、テストされていません...):

    private static int FindOddBall(int[] ary)
    {
        int l = 0,
            r = ary.Length - 1;
        int n = (l+r)/2;
        while (r > l+2)
        {
            n = (l + r) / 2;
            while (ary[n] == ary[n-1])
                n = FindBreakIndex(ary, l, n);
            if (n % 2 == 0) // even index we are on or to the left of the oddball 
                l = n;
            else            // odd index we are to the right of the oddball
                r = n-1;
        }
        return ary[l];
    }
    private static int FindBreakIndex(int[] ary, int l, int n)
    {
        var t = ary[n];
        var r = n;
        while(ary[n] != t || ary[n] == ary[n-1])
            if(ary[n] == t)
            {
                r = n;
                n = (l + r)/2;
            }
            else
            {
                l = n;
                n = (l + r)/2;
            }
        return n;
    }
于 2010-07-05T17:02:19.530 に答える
0

手がかりは、log(n) を探していることです。これは n 未満です。

一度に 1 つずつ配列全体をステップ実行しますか? それがNです。それはうまくいきません。

配列の最初の 2 つのインデックス (0 と 1) は同じ数値でなければならないことがわかっています。配列内の奇数がその後にある場合は、50 および 51 と同じです。

したがって、配列の中央の要素を見つけて、その直後の要素と比較します。数値の変更が間違ったインデックスで発生した場合、配列内の奇数がその前にあることがわかります。それ以外の場合は、後です。1 組の比較で、ターゲットが配列のどちらの半分にあるかを把握します。

そこから続けてください。

于 2010-07-12T17:20:00.647 に答える
0

これを試して：

int getOddOccurrence(int ar[], int ar_size)
{
     int i;
     int xor = 0; 
     for (i=0; i < ar_size; i++)     
        xor = xor ^ ar[i];

     return res;
}

XOR は、同じ数で XOR するたびにキャンセルされるため、1^1=0 ですが 1^1^1=1 なので、すべてのペアは奇数を除外してキャンセルする必要があります。

于 2015-10-16T15:43:53.830 に答える
0

ハッシュ テーブルを使用する

For each element E in the input set
    if E is set in the hash table
         increment it's value
    else        
         set E in the hash table and initialize it to 0

For each key K in hash table
    if K % 2 = 1
        return K

このアルゴリズムは 2n であるため、O(n) に属します。

于 2014-07-15T17:39:05.047 に答える
0

配列内の長さの分布、および配列全体の分布に関する情報はありませんよね?

したがって、arraylength は 1、11、101、1001 などで、1 には少なくとも上限がなく、(length-1)/2 + 1 要素までの少なくとも 1 つのタイプの要素 ('number') を含む必要があります。合計サイズが 1、11、101 の場合: 1、1 ～ 6、1 ～ 51 要素など。

可能なすべてのサイズが等しい確率であると仮定しますか? これは、サイズ/4 のサブアレイの中間の長さにつながりますよね?

サイズ 5 の配列は、1、2、または 3 つのサブリストに分割できます。

詳細に入ると、明らかなように見えることはそれほど明白ではありません。

サイズ 5 の配列は、1 つの方法で 1 つのサブリストに「分割」でき、それを「分割」と呼ぶ議論の余地のある権利があります。5 つの要素のリストです (aaaaa)。混乱を避けるために、リスト内の要素が数字 (a、b、c、...) ではなく、順序付けられた文字であると仮定しましょう。

2 つのサブリストに分割すると、(1, 4)、(2, 3)、(3, 2)、(4, 1) のようになります。(abbbb、aabbb、aaabb、aaaab)。

ここで、前に行われた主張を振り返ってみましょう: 「分割」(5) は、2 つのサブリストへの 4 つの分割と同じ確率であると想定されますか? それとも、それらを混ぜ合わせて、すべての分割の可能性が均等 (1/5) であると仮定しますか?

それとも、サブリストの長さの確率を知らずに解を計算できますか?

于 2010-07-05T21:36:33.723 に答える
-2

You can create a cummulative array and count how much each number occur and then in the cummulative array find the element which is odd. Example:

int a[]=new int[]{2,3,4,2,3,1,4,5,6,5,6,7,1};
int b[]=new int[1000];
for (int i=0;i<b.length;i++) {
    b[i]=0;
}
for (Int i=0;i<a.length;i++) {
    b[a[i]]++;
}
for (int i=0;i<b.length;i++) {
    if ( b[i]!=0) {
        if (b[i] %2==0) {
          system.out.println(i);  break;

    }
}
于 2010-07-07T13:38:35.873 に答える
-3

x[i] != x[i+1]; となる最小の偶数 i をバイナリ検索します。あなたの答えは x[i] です。

編集：公の要求により、ここにコードがあります

int f(int *x, int min, int max) {
  int size = max;
  min /= 2;
  max /= 2;
  while (min < max) {
    int i = (min + max)/2;
    if (i==0 || x[2*i-1] == x[2*i])
      min = i+1;
    else
      max = i-1;
  }
  if (2*max == size || x[2*max] != x[2*max+1])
    return x[2*max];
  return x[2*min];
}
于 2010-07-06T11:18:01.727 に答える