題目：

Given an array of numbers?nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given?nums = [1, 2, 1, 3, 2, 5], return?[3, 5].

Note:

The order of the result is not important. So in the above example,?[5, 3]?is also correct.

Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

鏈接：?http://leetcode.com/problems/single-number-iii/

題解：

昨晚卡到現在。但昨晚睡覺前google了一下，看到了幾篇文章以后才理解。還是需要加強bit manipulation。 歸根結底是大學時數字電路沒學好 -_____-!! 我不堪的本科生涯...略去一億字。

這里我們主要是先異或所有數字，得到 a^b， 因為a和b不相等，所以 a^b里至少有一個bit位k，k = 1。 然后我們就可以用這個第k位來進行判斷， 因為a和b里只有一個數第k位 = 1，我們對輸入數組所有第k位為1的數字進行異或，就可以找到第k位為1的僅出現一次的數字， 再用這個數字a和 a^b進行異或，我們也就求得了b。

Time Complexity - O(n)， Space Complexity - O(1)。

public class Solution {public int[] singleNumber(int[] nums) {int[] res = {-1, -1};if(nums == null || nums.length == 0) {return res;}int a_XOR_b = 0; for(int i = 0; i < nums.length; i++) { // find a ^ ba_XOR_b ^= nums[i];}int k = 0; // find one bit in a^b == 1for(int i = 0; i < 31; i++) { // that means only one num in a, b has 1 on kth bitif(((a_XOR_b >> i) & 1) == 1) {k = i;break;}}int a = 0;for(int i = 0; i < nums.length; i++) { // since only one num in a, b has 1 on kth bitif(((nums[i] >> k) & 1) == 1) { // we can XOR all nums has 1 on kth bita ^= nums[i]; // duplicate nums will be evened out }}int b = a ^ a_XOR_b;res[0] = a;res[1] = b;return res;} }

?

二刷：

也是用一刷一樣的方法，比較tricky

Java:

public class Solution {public int[] singleNumber(int[] nums) {int[] res = {-1, -1};if (nums == null || nums.length == 0) {return res;}int a_XOR_b = 0;for (int i : nums) {a_XOR_b ^= i;}int k = 0;for (int i = 0; i < 32; i++) {if (((a_XOR_b >> i) & 1) == 1) {k = i;break;}}res[0] = 0;for (int i : nums) {if (((i >> k) & 1) == 1) {res[0] ^= i;}}res[1] = a_XOR_b ^ res[0];return res;} }

?

題外話： ?

其實本科時，學校開設的課程挺不錯的，老師也努力務實，都怪自己沒把心思放在學習上。雖然專業是EE，但像什么基數排序，霍夫曼編碼，游程碼，最短路徑之類的東西，老師們也都多少介紹過。信息量很大，作業和考試也難。真要四年扎扎實實學下來的話，也不至于現在一把年紀了還在刷題。 過去的都過去了，接下來好好努力吧。

?

三刷:

這次就比較熟練了，嘗試一些不同的編程風格。 ?4/4/2016。

Java:

Time Complexity - O(n)， Space Complexity - O(1)。

public class Solution {public int[] singleNumber(int[] nums) {int[] res = new int[2];if (nums == null || nums.length < 2) return res;int a_xor_b = 0;for (int num : nums) { a_xor_b ^= num; }int diffIndex = 0;while (diffIndex < 32) {if (((a_xor_b >> diffIndex) & 1) == 1) { break; }diffIndex++;}int num1 = 0;for (int num : nums) {if (((num >> diffIndex) & 1) == 1) { num1 ^= num; }}res[0] = num1;res[1] = a_xor_b ^ num1;return res;} }

?

Update:

public class Solution {public int[] singleNumber(int[] nums) {if (nums == null || nums.length < 2) return new int[] {-1, -1};int a_XOR_b = 0;for (int num : nums) a_XOR_b ^= num;int k = 0;while (k < 31) {if (((a_XOR_b >> k) & 1) == 1) break;k++;}int a = 0;for (int num : nums) {if (((num >> k) & 1) == 1) a ^= num;}return new int[] {a, a ^ a_XOR_b};} }

?

?

Reference:

https://groups.google.com/forum/#!topic/pongba/9KCA7b484OE

https://groups.google.com/forum/#!topic/pongba/drV6dytcoJE

http://www.matrix67.com/blog/archives/511

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的260. Single Number III的全部內容，希望文章能夠幫你解決所遇到的問題。

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