本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖
面試題56：數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字
題目要求：
一個(gè)整數(shù)數(shù)組里除了兩個(gè)數(shù)字出現(xiàn)一次消痛，其他數(shù)字都出現(xiàn)兩次七芭。請(qǐng)找出這兩個(gè)數(shù)字拾稳。要求時(shí)間復(fù)雜度為o(n)，空間復(fù)雜度為o(1)。
解題思路：
這道題可以看成“數(shù)組中只出現(xiàn)一次的一個(gè)數(shù)字”的延伸。如果所有數(shù)字都出現(xiàn)兩次凌净，只有一個(gè)數(shù)字是出現(xiàn)1次，那么可以通過(guò)把所有所有進(jìn)行異或運(yùn)算解決屋讶。因?yàn)閤^x = 0冰寻。
但如果有兩個(gè)數(shù)字出現(xiàn)一次，能否轉(zhuǎn)化成上述問(wèn)題皿渗？依舊把所有數(shù)字異或斩芭，最終的結(jié)果就是那兩個(gè)出現(xiàn)一次的數(shù)字a,b異或的結(jié)果。因?yàn)閍乐疆，b不想等划乖，因此結(jié)果肯定不為0，那么結(jié)果的二進(jìn)制表示至少有一位為1诀拭，找到那個(gè)1的位置p迁筛，然后我們就可以根據(jù)第p位是否為1將所有的數(shù)字分成兩堆煤蚌，這樣我們就把所有數(shù)字分成兩部分耕挨，且每部分都是只包含一個(gè)只出現(xiàn)一次的數(shù)字细卧、其他數(shù)字出現(xiàn)兩次，從而將問(wèn)題轉(zhuǎn)化為最開始我們討論的“數(shù)組中只出現(xiàn)一次的一個(gè)數(shù)字”問(wèn)題筒占。
實(shí)例分析(以2,4,3,6,3,2,5,5為例)：
相關(guān)數(shù)字的二進(jìn)制表示為：
2 = 0010 3 = 0011 4 = 0100
5 = 0101 6 = 0110
步驟1 全體異或：2^4^3^6^3^2^5^5 = 4^6 = 0010
步驟2 確定位置：對(duì)于0010贪庙，從右數(shù)的第二位為1，因此可以根據(jù)倒數(shù)第2位是否為1進(jìn)行分組
步驟3 進(jìn)行分組：分成[2,3,6,3,2]和[4,5,5]兩組
步驟4 分組異或：2^3^6^3^2 = 6翰苫，4^5^5 = 4止邮，因此結(jié)果為4，6奏窑。
代碼實(shí)現(xiàn)：
package chapter6;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/17
* Time : 10:58
* Description:數(shù)組中數(shù)字出現(xiàn)的次數(shù)
* 有兩個(gè)數(shù)字分別出現(xiàn)一次导披，其他的都出現(xiàn)兩次，找到這兩個(gè)數(shù)字
**/
public class P275_NumberAppearOnce {
public static int[] findNumsAppearOnce(int[] data){
int result = 0;
for(int i=0;i<data.length;i++)
result^=data[i];
int indexOf1 = findFirstBit1(result);
int ret[] = new int[]{0,0};
if(indexOf1<0)
return ret;
for(int i=0;i<data.length;i++){
if((data[i]&indexOf1)==0)
ret[0]^=data[i];
else
ret[1]^=data[i];
}
return ret;
}
public static int findFirstBit1(int num){
if(num<0)
return -1;
int indexOf1 = 1;
while (num!=0){
if((num&1)==1)
return indexOf1;
else{
num = num>>1;
indexOf1*=2;
}
}
return -1;
}
public static void main(String[] args){
int[] data = new int[]{2,4,3,6,3,2,5,5};
int[] result = findNumsAppearOnce(data); // 4,6
System.out.println(result[0]);
System.out.println(result[1]);
}
}
運(yùn)行結(jié)果
4
6
