java - 時間 O(n) で配列内の重複する要素を見つける

Question

就職の面接でこの質問をされて、正しい答えをずっと考えていました。

0 から n-1 までの数値の配列があり、そのうちの 1 つが削除され、その数値の複製を作成する配列に既にある数値に置き換えられます。時間O(n)でこの重複をどのように検出できますか?

たとえば、の配列は4,1,2,3になり4,1,2,2ます。

時間O(n ² )の簡単な解決策は、ネストされたループを使用して各要素の複製を探すことです。

score 155 · Accepted Answer

これは、O(n)時間とO(1)空間で行うことができます。

(このアルゴリズムは、数値が既知の範囲内の連続した整数であるためのみ機能します):

ベクトルの 1 回のパスで、すべての数値の合計と、すべての数値の 2 乗の合計を計算します。

からすべての数値の合計を引きますN(N-1)/2。これを呼び出しますA。

から二乗和を引きN(N-1)(2N-1)/6ます。これをで割りAます。結果を呼び出しBます。

削除され(B + A)/2た番号はで、置き換えられた番号はです(B - A)/2。

例：

ベクトルは[0, 1, 1, 2, 3, 5]次のとおりです。

N = 6
ベクトルの合計は 0 + 1 + 1 + 2 + 3 + 5 = 12.N(N-1)/2 は 15.A = 3.
二乗和は 0 + 1 + 1 + 4 + 9 + 25 = 40. N(N-1)(2N-1)/6 は 55. B = (55 - 40)/A = 5.
削除された数は (5 + 3) / 2 = 4 です。
置き換えられた数は (5 - 3) / 2 = 1 です。

機能する理由:

元のベクトルの合計[0, ..., N-1]はですN(N-1)/2。値aが削除され、に置き換えられたとしbます。これで、修正されたベクトルの合計はになりますN(N-1)/2 + b - a。から修正されたベクトルの合計を引くと、がN(N-1)/2得られa - bます。だからA = a - b。
同様に、元のベクトルの平方和はですN(N-1)(2N-1)/6。修正されたベクトルの二乗和はです。元の合計から変更されたベクトルの二乗和を引くと、と同じになります。したがって、それを(つまり) で割ると、が得られます。N(N-1)(2N-1)/6 + b² - a²a² - b²(a+b)(a-b)a - bAB = a + b
今B + A = a + b + a - b = 2aとB - A = a + b - (a - b) = 2b。

score 34 · Accepted Answer

元の配列がありますタイプint A[N];の 2 番目の配列も作成します。最初の配列を反復し、false の場合は設定し、そうでない場合は bing!bool B[N]bool=falseB[A[i]]=true

score 32 · Accepted Answer

余分なスペースなしで O(N) 時間で実行できます。アルゴリズムの仕組みは次のとおりです。

次の方法で配列を反復処理します。

検出された各要素について、対応するインデックス値を負に設定します。例 : a[0] = 2 が見つかった場合。a[2] に移動し、値を否定します。

これを行うことで、遭遇するようにフラグを立てます。あなたは負の数を持つことができないことを知っているので、あなたはそれを否定した人であることも知っています.
値に対応するインデックスがすでに負のフラグが付いているかどうかを確認します。そうであれば、重複した要素を取得します。例: a[0]=2 の場合、a[2] に移動し、負かどうかを確認します。

次の配列があるとしましょう：

int a[]  = {2,1,2,3,4};

最初の要素の後、配列は次のようになります。

int a[] = {2,1,-2,3,4};

2 番目の要素の後、配列は次のようになります。

int a[] = {2,-1,-2,3,4};

3 番目の要素に到達すると、a[2] に移動し、既に負になっていることがわかります。複製を取得します。

score 11 · Accepted Answer

配列を 3 回スキャンします。

すべての配列要素を XOR します-> A. 0 から N-1 までのすべての数値を XOR します -> B. ここA XOR B = X XOR Dで、X は削除された要素、D は複製要素です。
でゼロ以外の任意のビットを選択しA XOR Bます。このビットが設定されているすべての配列要素を XOR します-> A1。このビットが設定されている 0 から N-1 までのすべての数値を XOR しますB1。今すぐまたはのいずれA1 XOR B1 = XかA1 XOR B1 = D。
アレイをもう一度スキャンして、を探します A1 XOR B1。見つかった場合、これは重複要素です。そうでない場合、重複する要素はA XOR B XOR A1 XOR B1です。

score 7 · Accepted Answer

a を使用して、HashSet既に表示されているすべての数値を保持します。(償却)O(1)時間で動作するため、合計はO(N)です。

score 7 · Accepted Answer

BitSet を使用することをお勧めします。N は配列のインデックス付けに十分小さいことがわかっているため、BitSet は適切なサイズになります。

配列の各要素について、その値に対応するビットを確認します。すでに設定されている場合は、重複しています。そうでない場合は、ビットを設定します。

score 4 · Accepted Answer

@rici は、時間と空間の使用について正しいです。「これは、O(n) 時間と O(1) 空間で実行できます。」

ただし、質問はより広い要件に拡張できます。重複する数字が 1 つだけである必要はなく、数字が連続していなくてもかまいません。

OJ はこのように説明しています: (注 3 は明らかに狭められる可能性があります)

n + 1 個の整数を含む配列 nums が与えられ、各整数が 1 から n (両端を含む) の間である場合、少なくとも 1 つの重複する数値が存在する必要があることを証明してください。重複する番号が 1 つだけあると仮定して、重複する番号を見つけます。

ノート：

配列を変更してはなりません (配列は読み取り専用であると仮定します)。

一定の O(1) 余分なスペースのみを使用する必要があります。

ランタイムの複雑さは O(n2) 未満である必要があります。

配列内の重複する数値は 1 つだけですが、複数回繰り返すことができます。

質問は、フロイドのサイクル発見アルゴリズムを使用して、キース・シュワルツによって非常によく説明され、ここで回答されています。

この問題を解決するために使用する必要がある主なトリックは、0 から n - 2 の範囲の n 個の要素の配列があるため、配列をセット {0, 1, ..., n - 1} それ自体に。この関数は f(i) = A[i] で定義されます。この設定により、複製された値は、f(i) = f(j) となるインデックス i != j のペアに対応します。したがって、私たちの課題は、このペア (i, j) を見つけることです。取得したら、f(i) = A[i] を選択するだけで、重複した値を簡単に見つけることができます。

しかし、この繰り返される値をどのように見つけるのでしょうか? これは、サイクル検出と呼ばれるコンピューターサイエンスでよく研究されている問題であることがわかりました。問題の一般的な形式は次のとおりです。関数 f が与えられます。シーケンス x_i を次のように定義します

    x_0     = k       (for some k)
    x_1     = f(x_0)
    x_2     = f(f(x_0))
    ...
    x_{n+1} = f(x_n)

f が定義域からそれ自体に写像すると仮定すると、この関数は 3 つの形式のいずれかになります。まず、ドメインが無限の場合、シーケンスは無限に長く、繰り返さない可能性があります。たとえば、整数に対する関数 f(n) = n + 1 には、このプロパティがあります。数値は重複しません。第 2 に、シーケンスは閉ループである可能性があります。これは、x_0 = x_i となる i があることを意味します。この場合、シーケンスは一定の値のセットを無期限に循環します。最後に、シーケンスは「ロー型」になる可能性があります。この場合、シーケンスは次のようになります。

 x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
                    ^                       |
                    |                       |
                    +-----------------------+

つまり、シーケンスは、サイクルに入る要素のチェーンで始まり、その後無限に循環します。シーケンスで到達するサイクルの最初の要素を、サイクルの「エントリ」とします。

Python の実装もここにあります。

def findDuplicate(self, nums):
    # The "tortoise and hare" step.  We start at the end of the array and try
    # to find an intersection point in the cycle.
    slow = 0
    fast = 0

    # Keep advancing 'slow' by one step and 'fast' by two steps until they
    # meet inside the loop.
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast:
            break

    # Start up another pointer from the end of the array and march it forward
    # until it hits the pointer inside the array.
    finder = 0
    while True:
        slow   = nums[slow]
        finder = nums[finder]

        # If the two hit, the intersection index is the duplicate element.
        if slow == finder:
            return slow

score 3 · Accepted Answer

ハッシュテーブルを使用します。ハッシュテーブルに要素を含めることは O(1) です。

score 2 · Accepted Answer

1 つの実用的なソリューション:

数値は整数であると仮定します

[0 .. N] の配列を作成する

int[] counter = new int[N];

次に、読み取りを繰り返し、カウンターをインクリメントします。

 if (counter[val] >0) {
   // duplicate
 } else {
   counter[val]++;
 }

score 0 · Accepted Answer

配列 O(n ln n) をソートします

スライディングウィンドウトリックを使用して配列 O(n) をトラバースする

スペースは O(1)

Arrays.sort(input);
for(int i = 0, j = 1; j < input.length ; j++, i++){
    if( input[i] == input[j]){
        System.out.println(input[i]);
        while(j < input.length && input[i] == input[j]) j++;
        i = j - 1;
    }
}

テストケース int[] { 1, 2, 3, 7, 7, 8, 3, 5, 7, 1, 2, 7 }

出力 1、2、3、7

score 0 · Accepted Answer

  public void duplicateNumberInArray {
    int a[] = new int[10];
    Scanner inp = new Scanner(System.in);
    for(int i=1;i<=5;i++){  
        System.out.println("enter no. ");
        a[i] = inp.nextInt();
    }
    Set<Integer> st = new HashSet<Integer>();
    Set<Integer> s = new HashSet<Integer>();
    for(int i=1;i<=5;i++){          
        if(!st.add(a[i])){
            s.add(a[i]);
        }
    }

    Iterator<Integer> itr = s.iterator();
                System.out.println("Duplicate numbers are");
    while(itr.hasNext()){
        System.out.println(itr.next());
    }
}

まず、 Scanner クラスを使用して整数の配列を作成します。次に、数値のループを繰り返し、数値をセットに追加できるかどうかを確認します (数値をセットに追加できるのは、その特定の数値がまだセットに含まれていない場合のみです。つまり、セットは重複する番号を許可しないことを意味します。ブール値を追加して返すvale 重複する値を追加する場合は FALSE)。いいえの場合。追加できないということは、重複していることを意味するので、後で印刷できるように、重複した番号を別のセットに追加します。重複した番号が数回繰り返される可能性があるため、重複した番号をセットに追加していることに注意してください。

score 0 · Accepted Answer

このプログラムは c# に基づいており、別のプログラミング言語を使用してこのプログラムを実行する場合は、まず配列を昇順で変更し、最初の要素と 2 番目の要素を比較する必要があります。等しい場合は、繰り返し数が見つかりました。プログラムは次のとおりです。

int[] array=new int[]{1,2,3,4,5,6,7,8,9,4};
Array.Sort(array);
for(int a=0;a<array.Length-1;a++)
{
  if(array[a]==array[a+1]
  {
     Console.WriteLine("This {0} element is repeated",array[a]);
   }
}
Console.WriteLine("Not repeated number in array");

score 0 · Accepted Answer

hashMap を効率的に使用できます。

Integer[] a = {1,2,3,4,0,1,5,2,1,1,1,};
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int x : a)
{
    if (map.containsKey(x))  map.put(x,map.get(x)+1);
    else map.put(x,1);
}

Integer [] keys = map.keySet().toArray(new Integer[map.size()]);
for(int x : keys)
{
    if(map.get(x)!=1)
    {
        System.out.println(x+" repeats : "+map.get(x));
    }
}

score -2 · Accepted Answer

int a[] = {2,1,2,3,4};

int b[] = {0};

for(int i = 0; i < a.size; i++)
{

    if(a[i] == a[i+1])
    {
         //duplicate found
         //copy it to second array
        b[i] = a[i];
    }
}

java - 時間 O(n) で配列内の重複する要素を見つける

24 に答える 24

例：

機能する理由:

Related

Reference