6

2 つの要素がペアになっていない n=2k+2 要素の配列があります。8 つの要素の配列の例: 1 2 3 47 3 1 2 0. "47" と "0" は配列内でペアになっていません。ペアになっていない要素が 1 つしかない配列がある場合、この問題は XOR で解決します。しかし、私は 2 つの不対要素を持っています! 私に何ができる?解決策は、O(n) 時間のパフォーマンスと O(1) の追加メモリです。

4

4 に答える 4

8

いくつかのヒント...

2パスかかります。まず、リストを調べて、すべての要素を一緒に XOR します。あなたが得るものを参照してください。そこから進みます。

編集:最初のパスの結果に関する重要な観察は、2つのペアになっていない要素が異なるビットのセットを示すことです。

于 2012-02-02T16:05:47.950 に答える
1

INT_MAX/8 バイトのメモリを使用します。配列を歩きます。各値に対応するビットを 1 で XOR します。インスタンスが 0 または 2 の場合、ビットは 0 になります。インスタンスが 1 つしかない場合は、設定されます。O(1) メモリ、O(N) 時間。

于 2012-02-02T16:02:32.913 に答える
1
  1. 配列をスキャンし、各数値とカウントをハッシュに入れます。
  2. count=1 の項目を再スキャンして見つけます。

これは O(n) です。

于 2012-02-02T20:21:37.673 に答える
0

これを試すことができます.O(n)時間かかります

        int xor = arr[0];
        int set_bit_no;
        int i;
        int x = 0; //First unpair number
        int y = 0; //second unpair number
        for (i = 1; i < n; i++)
            xor ^= arr[i];

        set_bit_no = xor & ~(xor-1);//Get the rightmost set bit in set_bit_no
        for (i = 0; i < n; i++)
        {
            if (arr[i] & set_bit_no) {
                //XOR of first set 
                x = x ^ arr[i];
            }
            else
            {
                //XOR of second set
                y = y ^ arr[i];
            }
        }

説明... arr[] = {2, 4, 7, 9, 2, 4} 1) すべての要素の XOR を取得します。xor = 2^4^7^9^2^4 = 14 (1110) 2) xor のセットされたビットが 1 つしかない数値を取得します。
一番右のセットビットは簡単に取れるのでそれを使ってみましょう。set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010 これで、set_bit_no は xor の右端のセット ビットとしてのみセットされます。3) 要素を 2 つのセットに分割し、各セットの要素の xor を実行すると
、繰り返しのない要素 7 と 9 が得られます。

于 2017-04-25T11:48:38.880 に答える