直線的でない時間では、ソートされた配列で複製を見つける

Question

今日、インタビュアーは私にこの質問をしました。私の即時の対応は、現在の要素と配列内の前の要素を比較するだけで、線形検索を行うことができたということでした。彼はその後、問題が線形ではない時間にどのように解決できるかを私に尋ねました。

仮定

• アレイ複製のみアレイのみnでの長さ数[0, n]、移入ある
• あり
• をソートされアレイ。

例アレイ：[0,1,2,3,4,5,6,7,8,8,9]

Iは分割統治を思い付くしようとしこれを解決するアルゴリズムはありますが、それが正しい答えであるとは確信していません。誰にもアイデアはありますか？

Answer 1

は修正バイナリサーチと（Nログ）Oで行うことができる：

スタートアレイの中央に：アレイは[IDX] < IDX重複がそうでなければ、右へ、左にある場合。すすぎ、繰り返します。

Answer 2

私はこれを解決するために分裂征服アルゴリズムを考え出しましたが、正しい答えではないと確信しています。

確かに、バイナリ検索を行うことができます。

arr[i/2] >= i/2の場合、複製はアレイの上半分に配置され、それ以外の場合は下半分に配置されます。 lowerとupper間のアレイは、各反復において半分にされているので

while (lower != upper) 
    mid = (lower + upper)/2 
    if (arr[mid] >= mid) 
     lower = mid 
    else 
     upper = mid-1 

は、アルゴリズムは、O（Nログ）で実行されます。

ideone.com demo in Java

Answer 3

全く数がアレイから欠落していない場合は、例のように、それはバイナリサーチで（ログn）Oでなんとかです。 a[i] < iの場合、複製はiの前になり、それ以外の場合はiの後になります。

不在つの数字と1個の重複がある場合、我々はまだa[i] < i場合、重複はi前でなければならず、a[i] > i場合、欠席数はiと後に重複する前でなければならないことを知っています。ただし、a[i] == iの場合は、番号が見つからない場合は、iまたはその両方の前に番号と重複が両方ともあるかどうかはわかりません。iの後です。その場合、私はサブ線形アルゴリズムのための方法を見ません。

Answer 4

例の配列はあなたの質問と少し異なります。 nは配列の長さであり、配列中に唯一の重複があるので、配列内の各要素の値は[0、n-1]でなければなりません。それが本当であれば

は、この質問はO（n）の時間とO（1）スペース内の重複を見つける必要がありHow to find a duplicate element in an array of shuffled consecutive integers?

次のコードと同じものです。

public static int findOnlyDuplicateFromArray(int[] a, boolean startWithZero){ 
    int xor = 0; 
    int offset = 1; 
    for(int i=0; i < a.length; i++){ 
     if(startWithZero) 
      xor = xor^(a[i] + offset)^i; 
     else 
      xor = xor^a[i]^i; 
     } 
     if(startWithZero) 
      xor = xor - offset; 
    return xor; 
} 

Answer 5

どうですか？ 0からn-1までの自然数の所定のアレイ素子との和の和との間の（再帰スタイル）

public static int DuplicateBinaryFind(int[] arr, int left, int right) 
{ 
    int dup =0; 

    if(left==right) 
    { 
     dup = left; 
    } 
    else 
    { 
     int middle = (left+right)\2; 
     if(arr[middle]<middle) 
     { 
      dup = DuplicateBinaryFind(arr,left, middle-1); 

     } 
     else 
     { 
      dup = DuplicateBinaryFind(arr, middle+1, right); 
     } 
    } 

    return dup; 

} 

Answer 6

違いはあなた重複要素を与えます。 0からn-1要素の和は（N * N-1）/ 2 です。例配列は[0,1,2,3,4,5,6,7,8,8,9] の合計です。 45 配列要素の合計：53 53-45 = 8複製された要素はどれですか