#84 Single Number III

题目描述：

Given 2*n + 2 numbers, every numbers occurs twice except two, find them.

Have you met this question in a real interview?  Yes Example

Given [1,2,2,3,4,4,5,3] return 1 and 5

Challenge 

O(n) time, O(1) extra space.

题目思路：

这题还有点意思，其实思路是#82的follow-up。#82用两两异或的办法找到了单身狗，但是这题单身狗有两只，两两异或最终得到的是num1 ^ num2. 怎么利用这个结果呢？首先，这个结果肯定不为0，那么不为0，从二进制表达上，肯定有一些bit是1的。找到任意一个bit为1的位置，这就是num1和num2的difference所在。利用这个位置，可以把A分成两部分：这个位置的bit是1（比如把它们这类数归在num1的阵营），这个位置的bit是0（把它们这类数归在num2的阵营）。各自在两个阵营中再做异或，就可以得到两只单身狗了。

Mycode（AC = 239ms）：

class Solution { public: /** * @param A : An integer array * @return : Two integers */ vector<int> singleNumberIII(vector<int> &A) { // write your code here vector<int> ans(2, 0); if (A.size() <= 1) return ans; // find number 1 ^ number 2 int bitm = A[0]; for (int i = 1; i < A.size(); i++) { bitm ^= A[i]; } // find the different bit in number 1 and 2 int diff = 0; while (bitm % 2 == 0) { bitm >>= 1; diff++; } // classify numbers in A, and find number 1 and 2 // separately for (int i = 0; i < A.size(); i++) { if ((A[i] >> diff) % 2 == 0) { ans[0] ^= A[i]; } else { ans[1] ^= A[i]; } } return ans; } };