# Single Number III ### Source - lintcode: [(84) Single Number III](http://www.lintcode.com/en/problem/single-number-iii/) ~~~ Given 2*n + 2 numbers, every numbers occurs twice except two, find them. Example Given [1,2,2,3,4,4,5,3] return 1 and 5 Challenge O(n) time, O(1) extra space. ~~~ ### 題解 題 [Single Number](http://algorithm.yuanbin.me/zh-cn/math_and_bit_manipulation/single_number.html) 的 follow up, 不妨設最后兩個只出現一次的數分別為 `x1, x2`. 那么遍歷數組時根據兩兩異或的方法可得最后的結果為 `x1 ^ x2`, 如果我們要分別求得 `x1` 和 `x2`, 我們可以根據 `x1 ^ x2 ^ x1 = x2` 求得 `x2`, 同理可得 `x_1`. 那么問題來了，如何得到`x1`和`x2`呢？看起來似乎是個死循環。大多數人一般也就能想到這一步(比如我...)。 這道題的巧妙之處在于利用`x1 ^ x2`的結果對原數組進行了分組，進而將`x1`和`x2`分開了。具體方法則是利用了`x1 ^ x2`不為0的特性，如果`x1 ^ x2`不為0，那么`x1 ^ x2`的結果必然存在某一二進制位不為0（即為1），我們不妨將最低位的1提取出來，由于在這一二進制位上`x1`和`x2`必然相異，即`x1`, `x2`中相應位一個為0，另一個為1，所以我們可以利用這個最低位的1將`x1`和`x2`分開。又由于除了`x1`和`x2`之外其他數都是成對出現，故與最低位的1異或時一定會抵消，十分之精妙！ ### Java ~~~ public class Solution { /** * @param A : An integer array * @return : Two integers */ public List<Integer> singleNumberIII(int[] A) { ArrayList<Integer> nums = new ArrayList<Integer>(); if (A == null || A.length == 0) return nums; int x1xorx2 = 0; for (int i : A) { x1xorx2 ^= i; } // get the last 1 bit of x1xorx2, e.g. 1010 ==> 0010 int last1Bit = x1xorx2 - (x1xorx2 & (x1xorx2 - 1)); int single1 = 0, single2 = 0; for (int i : A) { if ((last1Bit & i) == 0) { single1 ^= i; } else { single2 ^= i; } } nums.add(single1); nums.add(single2); return nums; } } ~~~ ### 源碼分析 求一個數二進制位1的最低位方法為 `x1xorx2 - (x1xorx2 & (x1xorx2 - 1))`, 其他位運算的總結可參考 [Bit Manipulation](http://algorithm.yuanbin.me/zh-cn/basics_misc/bit_manipulation.html)。利用`last1Bit`可將數組的數分為兩組，一組是相應位為0，另一組是相應位為1. ### 復雜度分析 兩次遍歷數組，時間復雜度 O(n)O(n)O(n), 使用了部分額外空間，空間復雜度 O(1)O(1)O(1). ### Reference - [Single Number III 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/single-number-iii/)