題目描述
一個(gè)整型數(shù)組 nums 里除兩個(gè)數(shù)字之外褂始，其他數(shù)字都出現(xiàn)了兩次鲜结。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字普泡。要求時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)咙边。
題解一
先將數(shù)組排序猜煮，然后再找出現(xiàn)一次的數(shù)字是比較簡(jiǎn)單的次员。
時(shí)間復(fù)雜度為，空間復(fù)雜度為
王带。比較簡(jiǎn)單翠肘，代碼省略。
題解二
還有一種想法是以空間換時(shí)間辫秧，使用一個(gè)哈希表來記錄數(shù)組中每個(gè)數(shù)字出現(xiàn)的次數(shù)，最終可以得到兩個(gè)只出現(xiàn)一次的數(shù)字被丧。
時(shí)間復(fù)雜度為盟戏，空間復(fù)雜度為
。比較簡(jiǎn)單甥桂，代碼省略柿究。
題解三
重頭戲來了，我們可以在時(shí)間復(fù)雜度為的情況下黄选，將空間復(fù)雜度降低至
蝇摸。如果將這道題改為數(shù)組中只有一個(gè)數(shù)字只出現(xiàn)一次，那么問題就簡(jiǎn)單了办陷。我們可以利用異或運(yùn)算（相同為0貌夕，不同為1）的性質(zhì)：
- 任何一個(gè)數(shù)字異或它自己都等于0。
- 異或運(yùn)算具有交換律民镜。
因此啡专，如果我們依次遍歷異或數(shù)組中的每個(gè)數(shù)字，那么最終出現(xiàn)的結(jié)果就是那個(gè)只出現(xiàn)一次的數(shù)字（因?yàn)槠渌嗤臄?shù)字進(jìn)行異或運(yùn)算之后都是0制圈，全部抵消了）们童。
但是由于這道題中有兩個(gè)數(shù)字只出現(xiàn)一次，所以問題會(huì)復(fù)雜一點(diǎn)鲸鹦，但是我們依舊可以將它化解為一個(gè)數(shù)字的情形慧库。只要將原數(shù)組拆成兩個(gè)數(shù)組，每個(gè)數(shù)組都包含一個(gè)只出現(xiàn)一次的數(shù)字即可馋嗜。
我們還是從頭到尾一次遍歷異或數(shù)組中的每個(gè)數(shù)字齐板，最終會(huì)得到那兩個(gè)只出現(xiàn)一次的數(shù)字的異或結(jié)果。而這個(gè)結(jié)果的二進(jìn)制表示中至少有一位為1葛菇，假設(shè)我們?cè)诮Y(jié)果中找到第一個(gè)為1的位的位置覆积，記為index，那么就可以對(duì)于所有數(shù)字按照這個(gè)位是否為1劃分為兩部分熟呛。
建立兩個(gè)數(shù)組宽档，分別保存拆成兩個(gè)數(shù)組之后的結(jié)果。因?yàn)槟莾蓚€(gè)只出現(xiàn)一次的數(shù)在index位上異或結(jié)果為1（對(duì)于異或庵朝，相同為0吗冤，不同為1）又厉，說明這兩個(gè)數(shù)在index位上是不一樣的。
使用這個(gè)判斷條件椎瘟，可以將整個(gè)數(shù)組分為兩類覆致。第一類子數(shù)組中每個(gè)數(shù)字的index位都為1，第二類子數(shù)組中每個(gè)數(shù)字的index位都為0肺蔚。這樣同時(shí)也將兩個(gè)只出現(xiàn)一次的數(shù)給分開了煌妈，而且同時(shí)保證相同的數(shù)處于同一個(gè)數(shù)組中（相同的數(shù)index位一定相同）。為了方便實(shí)現(xiàn)宣羊，我自己寫了個(gè)getFullBinaryString()函數(shù)璧诵。
得到兩個(gè)數(shù)組之后，我們就將這個(gè)問題轉(zhuǎn)化為求數(shù)組中一個(gè)數(shù)字出現(xiàn)一次的問題了仇冯。
時(shí)間復(fù)雜度為之宿，空間復(fù)雜度為
。
這樣說有點(diǎn)抽象苛坚，舉個(gè)例子比被，假設(shè)輸入的數(shù)組為{1,2,10,4,1,4,3,3}，依次對(duì)數(shù)組中每一個(gè)數(shù)字進(jìn)行異或運(yùn)算之后泼舱，得到的二進(jìn)制結(jié)果為1000等缀。第一位為1，于是我們將index設(shè)置成1娇昙，我們根據(jù)每個(gè)數(shù)字的index位是否為1將數(shù)組分為兩部分项滑，分別得到兩個(gè)數(shù)組 和 。接下來分別對(duì)兩個(gè)數(shù)組求異或就可以得到兩個(gè)只出現(xiàn)一次的數(shù)字2和10了涯贞。
下面是參考代碼：
import java.math.BigInteger;
import java.util.*;
class Solution {
public int[] singleNumbers(int[] nums) {
// 得到兩個(gè)只出現(xiàn)一次的數(shù)字的異或結(jié)果
int resXOR = 0;
for (int num : nums)
resXOR ^= num;
String resXORString = getFullBinaryString(resXOR);
// 計(jì)算第一個(gè)為1的位的位置枪狂，據(jù)此將原數(shù)組劃分為兩個(gè)數(shù)組
int index = 0;
for (int i = 1; i < 32; i++) {
if (resXORString.charAt(i) == '1') {
index = i;
break;
}
}
// 劃分?jǐn)?shù)組
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
for (int num : nums) {
String numString = getFullBinaryString(num);
if (numString.charAt(index) == '1')
list1.add(num);
else list2.add(num);
}
return new int[] {findUnique(list1), findUnique(list2)};
}
public int findUnique(ArrayList<Integer> list) {
int res = 0;
for (int num : list) {
res ^= num;
}
return res;
}
public String getFullBinaryString(int num) {
String s = Integer.toBinaryString(num);
return String.format("%032d", new BigInteger(s));
}
}
