題目描述
給你一個(gè)數(shù)組茧痕，除了x,數(shù)組中每個(gè)元素出現(xiàn)2次,讓你求解出這個(gè)x故黑。
[leetcode136]https://leetcode.com/problems/single-number/
思路
- 使用hashMap是非常容易理解并求解的不再累述。
- 接下來(lái)就是我們的位操作，這一類題的一個(gè)通用的解法。
算法步驟
對(duì)這個(gè)數(shù)組的每一位進(jìn)行異或亏吝，最后的結(jié)果就是那個(gè)單數(shù)來(lái)的數(shù)岭埠。
算法原理
異或操作滿足：ab=ba,aa=0,0a=a
所以一趟異或操作之后盏混，那些出現(xiàn)偶數(shù)次的數(shù)對(duì)結(jié)果的貢獻(xiàn)就沒(méi)有影響，這些所有的出現(xiàn)偶數(shù)次的數(shù)異或之后為0惜论，而0與那個(gè)單獨(dú)出現(xiàn)的數(shù)x異或之后就為x许赃。
算法代碼
public class Solution {
public int singleNumber(int[] nums) {
int res=0;
for(int i:nums)
res^=i;
return res;
}
}
算法原理很簡(jiǎn)單，實(shí)現(xiàn)也很簡(jiǎn)單馆类。但這里需要注意的是混聊，那些出現(xiàn)多次的必須是出現(xiàn)偶數(shù)次，不然這個(gè)算法就失效了乾巧，那么對(duì)于出現(xiàn)奇數(shù)次的怎么辦呢句喜？接下來(lái)拓展詳細(xì)描述這一類題目的解法。
拓展一
[leetcode]https://leetcode.com/problems/single-number-ii/
這次數(shù)組中除了x外沟于，每個(gè)元素出現(xiàn)3次咳胃，需要你找出x。注意到次數(shù)3為奇數(shù)了旷太，上述方法失效展懈。
思路
- 當(dāng)然了也可以使用一個(gè)hash,類似于上題的hash解法销睁，不用改動(dòng)代碼即可實(shí)現(xiàn)。當(dāng)然了存崖，這種解法很low冻记。不在詳述。
public class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(!hashMap.containsKey(nums[i]))
hashMap.put(nums[i],1);
else
hashMap.put(nums[i],2);
}
for(int i=0;i<nums.length;i++){
if(hashMap.get(nums[i])==1)
return nums[i];
}
return -1;
}
}
- 使用位操作
接下來(lái)介紹三種使用位操作的方法来惧，其實(shí)他們的本質(zhì)是一樣的冗栗。
位操作方法一
算法步驟
- 因?yàn)閕nt是32位，所以我們考慮使用一個(gè)長(zhǎng)度為32的數(shù)組供搀，初始化為0贞瞒。
- 記res為最后的結(jié)果，由于res也為32位的int趁曼，我們只需要確定军浆，res的每一位為1還是0即可，所以這里使用了一個(gè)外層32次的循環(huán)挡闰，內(nèi)層函數(shù)每執(zhí)行一次乒融，確定了res的一個(gè)比特位。
- 假設(shè)現(xiàn)在需要確定res的第i比特位摄悯，內(nèi)層函數(shù)找出原數(shù)組中在第i比特位上為1的數(shù)赞季，統(tǒng)計(jì)這些數(shù)的個(gè)數(shù)，然后對(duì)3取模奢驯，結(jié)果要么是0申钩，要么是1(因?yàn)楸绢}中那個(gè)特殊的數(shù)只出現(xiàn)一次)這個(gè)結(jié)果就是我們的res的第i比特位的值。
- 32趟走完時(shí)候我們可以確定res的每一個(gè)比特位是0還是是1瘪阁，也就可以確定res的值了撒遣。
算法原理
因?yàn)樵瓟?shù)組中除了數(shù)res外，每個(gè)數(shù)都出現(xiàn)三次管跺，所以我考察這些數(shù)的對(duì)應(yīng)比特位义黎。那些出現(xiàn)三次的數(shù)，對(duì)應(yīng)為1的比特位相加后為3的倍數(shù)豁跑，只有這個(gè)只出現(xiàn)1次的數(shù)的那些為1的bit位廉涕，這些位數(shù)上count為3n+1，所以我們相加取模時(shí)候就可以確定哪些比特位為1艇拍。
比如[1,2,2,2,3,3,3]
num a b
1 -> 0 1
2 -> 1 0
3 -> 1 1
2和3都出現(xiàn)了三次狐蜕，所以我們把對(duì)應(yīng)比特位1的個(gè)數(shù)相加的話a比特位一共6個(gè)1，b比特位一共4個(gè)1,對(duì)3取模后a比特為0卸夕，b比特位1层释。我們就知道結(jié)果為0。
算法代碼
public class Solution {
public int singleNumber(int[] nums) {
int[] count=new int[32];
int res=0;
for(int i=0;i<32;i++){
for(int j=0;j<nums.length;j++){
if(((nums[j]>>i)&1)==1)
count[i]++;
}
res|=((count[i]%3)<<i);
}
return res;
}
}
//當(dāng)然娇哆，一般化湃累，假如出現(xiàn)多次的數(shù)出現(xiàn)次數(shù)為k勃救，只需要模k即可。
//另外治力，如果那個(gè)特殊的數(shù)不是出現(xiàn)1次蒙秒，
//修改res|=((count[i]%3)<<i)即可，
//例如假如出現(xiàn)2次宵统，
//只需要修改為res|=((count[i]%3==0?0:1)<<i)
位操作方法二
算法步驟
- 使用三個(gè)變量晕讲，ones twos xthree，如果二進(jìn)制表示中马澈，某個(gè)數(shù)位上"1"出現(xiàn)一次瓢省，那么ones在這個(gè)數(shù)位上就是"1"，同理twos表示出現(xiàn)兩次痊班。
- 看看ones twos 的變化規(guī)則勤婚。新進(jìn)來(lái)一個(gè)數(shù)nums[i]，考察ones&nums[i],如果ones在這個(gè)比特位上為1涤伐，表面之前這個(gè)比特位"1"出現(xiàn)過(guò)一次馒胆，現(xiàn)在nums[i]在這個(gè)比特位上又為1，那么自然就是出現(xiàn)了兩次"1"凝果，所以twos在這個(gè)比特位上就應(yīng)該為1祝迂。ones的變化規(guī)則很簡(jiǎn)單，異或就行了器净。需要注意的是如果某個(gè)比特位在ones和twos中都為1,那么就代表出現(xiàn)了三次型雳，需要把這個(gè)比特位清零。
- 遍歷結(jié)束后山害，ones就是出現(xiàn)一次的數(shù)纠俭，twos就是出現(xiàn)兩次的數(shù)。
算法原理
從比特位來(lái)考慮粗恢，出現(xiàn)三次的數(shù)在遍歷結(jié)束之后對(duì)ones和twos都沒(méi)有影響柑晒，因?yàn)樗麄冏詈髸?huì)在他們比特位表示為"1"的位置上出現(xiàn)三次欧瘪，他們的影響被代碼
xthree = ~(ones & twos);
ones&=xthree;
twos&=xthree;
抹去眷射，最后ones的各個(gè)比特位就是只出現(xiàn)一次的那個(gè)數(shù)的比特位，twos的各個(gè)比特位就是只出現(xiàn)兩次的那個(gè)數(shù)的比特位佛掖。
算法代碼
public class Solution {
public int singleNumber(int[] nums) {
//2,2,3,2
int ones=0;//二進(jìn)制表示中“1”出現(xiàn)一次的數(shù)位
int twos=0;//二進(jìn)制表示中“1”出現(xiàn)兩次的數(shù)位
int xthree=0;
for(int i=0;i<nums.length;i++){
twos|=(ones&nums[i]);//出現(xiàn)兩次妖碉，當(dāng)然是“之前”位置上首先就是“1”（ones），然后輸入的數(shù)樹(shù)在這個(gè)位置上又是“1”
ones^=nums[i];//出現(xiàn)一次芥被，當(dāng)然是異或就行了欧宜，這樣出現(xiàn)一次的變?yōu)?，出現(xiàn)0次的變?yōu)?
xthree = ~(ones & twos);//一個(gè)數(shù)位在ones和twos同時(shí)為1拴魄，表示當(dāng)前數(shù)位出現(xiàn)了3次冗茸，應(yīng)該把這個(gè)數(shù)位變?yōu)?
ones&=xthree;
twos&=xthree;
}
return ones;
}
}
//拓展席镀，two最終記錄的是出先兩次的
//http://www.cnblogs.com/daijinqiao/p/3352893.html
//[1,2,2,2,3,3,4,4,4,5,5,5]
//[1,2,2,3,3,3,4,4,4,5,5,5]
位操作方法三
這個(gè)方法其實(shí)和方法二一樣，只不過(guò)搞得有點(diǎn)像數(shù)電設(shè)計(jì)中的狀態(tài)轉(zhuǎn)移夏漱。
算法步驟&原理
a表示32位的int豪诲，a的每一位怎么確定，在遍歷原數(shù)組過(guò)程中挂绰，考察原數(shù)組中數(shù)的比特位表示屎篱，如果該位上"1" 出現(xiàn)次數(shù)為2，那么該位就為1葵蒂，否則為0
同理
a表示32位的int交播，b的每一位怎么確定，在遍歷原數(shù)組過(guò)程中践付，考察原數(shù)組中數(shù)的比特位表示秦士，如果該位上"1" 出現(xiàn)次數(shù)為1，那么該位就為1永高，否則為0
那么我們很容易得到下面的狀態(tài)轉(zhuǎn)移表
(ai為a的i比特位伍宦，bi為b的i比特位,ci為新遍歷到的數(shù)的i比特位)
ai bi ci ai’ bi'
0 0 0 0 0
0 1 0 0 1
1 0 0 1 0
0 0 1 0 1
0 1 1 1 0
1 0 1 0 0
我們需要找到出現(xiàn)次數(shù)為1的比特位，也就是bi'為1
順便找到出現(xiàn)次數(shù)為2的比特位乏梁，也就是ai'為1
所以ai'=aibici|~aibici
bi'=aibici|aibici
我們就可以確定出現(xiàn)次數(shù)為1的比特位次洼，也就可以確定出現(xiàn)次數(shù)為1的數(shù)。
這里的代碼是同時(shí)找了次數(shù)為1的和為2的（這種理解是特殊的數(shù)出現(xiàn)一次或兩次遇骑，二者選其一）
算法代碼
public class Solution {
public int singleNumber(int[] nums) {
int a=0;
int b=0;
for(int c:nums){
int tmpa=a&(~b)&(~c)|((~a)&b&c);
b=(~a&~b&c)|(~a&b&~c);
a=tmpa;
}
return a|b;
}
}
當(dāng)然卖毁，如果了解轉(zhuǎn)臺(tái)轉(zhuǎn)移化簡(jiǎn)的話,可以簡(jiǎn)化為
for(int c:nums){
int tmpa=a&(~c)|(b&c);
b=(~a&~b&c)|(b&~c);
a=tmpa;
}
拓展二
[leetcode260]https://leetcode.com/problems/single-number-iii/
這次是數(shù)組中有兩個(gè)不同的數(shù)都只出現(xiàn)過(guò)一次，其他數(shù)都出現(xiàn)兩次落萎，讓找出這兩個(gè)數(shù)亥啦。
算法描述
- 對(duì)這些數(shù)進(jìn)行異或操作得到ones
- 移位與操作得到once的比特位表示的第一個(gè)非“0”位置，并把一個(gè)數(shù)賦值為僅該位置為1练链，其他位置為0
- 用這個(gè)數(shù)去和數(shù)組中的數(shù)做與運(yùn)算翔脱，根據(jù)與運(yùn)算結(jié)果是否為0可以把原數(shù)組中的數(shù)分為兩個(gè)陣營(yíng)，分別對(duì)兩個(gè)陣營(yíng)進(jìn)行異或操作媒鼓，最終得到的兩個(gè)結(jié)果就是所求的兩個(gè)數(shù)届吁。
算法原理
有兩個(gè)數(shù)a,b只出現(xiàn)一次，其他兩次绿鸣，那么所有數(shù)進(jìn)行異或之后的結(jié)果ones疚沐，ones比特位表示為1的位置肯定就是a和b在這個(gè)位置為一個(gè)1一個(gè)0，那么就可以使用這個(gè)位置把a(bǔ)和b分到不同的陣營(yíng)中潮模，兩個(gè)陣營(yíng)都是包含a/b和一堆成對(duì)出現(xiàn)的數(shù)亮蛔，對(duì)他們進(jìn)行異或操作即可求出a/b。
算法代碼
public class Solution {
public int[] singleNumber(int[] nums) {
int one=0;
for(int i:nums)
one^=i;
int tmp=1;
while((one&1)!=1){
one>>=1;
tmp<<=1;
}
int res1=0;
int res2=0;
for(int i:nums){
if((i&tmp)==0){
res1^=i;
}
else
res2^=i;
}
int[] res=new int[2];
res[0]=res1;
res[1]=res2;
return res;
}
}
當(dāng)然了擎厢，繼續(xù)拓展的話究流，如果有兩個(gè)數(shù)出現(xiàn)1次辣吃，其他書(shū)出現(xiàn)三次，那么就是拓展一中的方法先找到為出現(xiàn)次數(shù)為1的兩個(gè)數(shù)共同影響產(chǎn)生的結(jié)果ones,然后找到一個(gè)為“1”的比特位芬探，然后分陣營(yíng)齿尽，就變?yōu)閮蓚€(gè)拓展一類型的問(wèn)題。
如果一個(gè)一次一個(gè)兩次其他三次灯节，那么一次的就是ones,兩次的就是twos循头。
