84-落单的数 III

给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。

样例

给出 [1,2,2,3,4,4,5,3]，返回 1和5

挑战

O(n)时间复杂度，O(1)的额外空间复杂度

标签

贪心 LintCode 版权所有

思路

对于2*n+1个数字用异或就可以，参见博客LintCode-82.落单的数，而在此题将所有数异或之后得到的是两个落单的数的异或结果，没办法将结果拆分成两个落单的数。但因为两个落单数不同，所以肯定存在某个位k，使得两落单数在第k位上一个为0另一个为1（怎么找到这个k? 找异或结果中1出现的位置即可）。只需找到最小的这个k，然后将在k位上为0的所有数做异或得出其中一个落单的数，在k位为1的所有数也做另外的异或，得出另一个落单的数，这样最终可以得到两个落单的数。

code

class Solution {

public:

    /**

     * @param A : An integer array

     * @return : Two integers

     */

    vector<int> singleNumberIII(vector<int> &A) {

        // write your code here

        int size = A.size(), ans = 0, i = 0;

        vector<int> res;

        int r1 = 0, r2 = 0, k = 0;

        for(i=0; i<size; ++i) {

            ans ^= A[i];

        }

        while(ans % 2 == 0) {

            k++;

            ans >>= 1;

        }

        for(i=0; i<size; i++) {

            int kbit = ( A[i] >> k ) % 2;

            if(kbit == 0) {

                r1 ^= A[i];

            }

            else {

                r2 ^= A[i];

            }

        }

        res.push_back(r1);

        res.push_back(r2);

        return res;

    }

};