給出2*n + 2個的數字。除當中兩個數字之外其它每一個數字均出現兩次，找到這兩個數字。

您在真實的面試中是否遇到過這個題？? Yes 例子

給出?[1,2,2,3,4,4,5,3]。返回 1和5

挑戰

O(n)時間復雜度，O(1)的額外空間復雜度

標簽?Expand??

相關題目?Expand?

分析：這樣的抖靈巧的題要是面試官面我，我肯定會批判一番的！把全部數亦或下，得到的數能夠求出兩不同數的亦或值，這樣能夠找到一個位，在該位上能夠把全部數分成兩部分。沒部分能夠套用之前的“全部數都出現兩次，除了當中一個數”的代碼。

代碼：

class Solution { public:/*** @param A : An integer array* @return : Two integers*/vector<int> singleNumberIII(vector<int> &A) {// write your code hereint k = findFirstDiffBit(A);int ret1 = findOne(A, k, true);int ret2 = findOne(A, k, false);vector<int> ret;ret.push_back(ret1);ret.push_back(ret2);return ret;}int findFirstDiffBit(vector<int>& A){int x = 0;for (auto i : A)x ^= i;for (int i = 0;i<32;i++){if ((1 << i)&x)return i;}}int findOne(vector<int>&A, int k, bool first){int ret = 0;for (auto x : A){if (first){if ((1 << k)&x)ret ^= x;}else{if (((x>>k)&1) == 0)ret ^= x;}}return ret;} };

總結

以上是生活随笔為你收集整理的LintCode-落单的数 III的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。