題目描述
給你一個數(shù)組，除了x,數(shù)組中每個元素出現(xiàn)2次,讓你求解出這個x。
[leetcode136]https://leetcode.com/problems/single-number/
思路
- 使用hashMap是非常容易理解并求解的不再累述。
- 接下來就是我們的位操作，這一類題的一個通用的解法。
算法步驟
對這個數(shù)組的每一位進行異或，最后的結(jié)果就是那個單數(shù)來的數(shù)。
算法原理
異或操作滿足：ab=ba,aa=0,0a=a
所以一趟異或操作之后，那些出現(xiàn)偶數(shù)次的數(shù)對結(jié)果的貢獻就沒有影響，這些所有的出現(xiàn)偶數(shù)次的數(shù)異或之后為0，而0與那個單獨出現(xiàn)的數(shù)x異或之后就為x。
算法代碼
public class Solution {
public int singleNumber(int[] nums) {
int res=0;
for(int i:nums)
res^=i;
return res;
}
}
算法原理很簡單，實現(xiàn)也很簡單。但這里需要注意的是，那些出現(xiàn)多次的必須是出現(xiàn)偶數(shù)次，不然這個算法就失效了，那么對于出現(xiàn)奇數(shù)次的怎么辦呢？接下來拓展詳細描述這一類題目的解法。
拓展一
[leetcode]https://leetcode.com/problems/single-number-ii/
這次數(shù)組中除了x外，每個元素出現(xiàn)3次，需要你找出x。注意到次數(shù)3為奇數(shù)了，上述方法失效。
思路
- 當然了也可以使用一個hash,類似于上題的hash解法，不用改動代碼即可實現(xiàn)。當然了，這種解法很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;
}
}
- 使用位操作
接下來介紹三種使用位操作的方法，其實他們的本質(zhì)是一樣的。
位操作方法一
算法步驟
- 因為int是32位，所以我們考慮使用一個長度為32的數(shù)組，初始化為0。
- 記res為最后的結(jié)果，由于res也為32位的int，我們只需要確定，res的每一位為1還是0即可，所以這里使用了一個外層32次的循環(huán)，內(nèi)層函數(shù)每執(zhí)行一次，確定了res的一個比特位。
- 假設現(xiàn)在需要確定res的第i比特位，內(nèi)層函數(shù)找出原數(shù)組中在第i比特位上為1的數(shù)，統(tǒng)計這些數(shù)的個數(shù)，然后對3取模，結(jié)果要么是0，要么是1(因為本題中那個特殊的數(shù)只出現(xiàn)一次)這個結(jié)果就是我們的res的第i比特位的值。
- 32趟走完時候我們可以確定res的每一個比特位是0還是是1，也就可以確定res的值了。
算法原理
因為原數(shù)組中除了數(shù)res外，每個數(shù)都出現(xiàn)三次，所以我考察這些數(shù)的對應比特位。那些出現(xiàn)三次的數(shù)，對應為1的比特位相加后為3的倍數(shù)，只有這個只出現(xiàn)1次的數(shù)的那些為1的bit位，這些位數(shù)上count為3n+1，所以我們相加取模時候就可以確定哪些比特位為1。
比如[1,2,2,2,3,3,3]
num a b
1 -> 0 1
2 -> 1 0
3 -> 1 1
2和3都出現(xiàn)了三次，所以我們把對應比特位1的個數(shù)相加的話a比特位一共6個1，b比特位一共4個1,對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;
}
}
//當然，一般化，假如出現(xiàn)多次的數(shù)出現(xiàn)次數(shù)為k，只需要模k即可。
//另外，如果那個特殊的數(shù)不是出現(xiàn)1次，
//修改res|=((count[i]%3)<<i)即可，
//例如假如出現(xiàn)2次，
//只需要修改為res|=((count[i]%3==0?0:1)<<i)
位操作方法二
算法步驟
- 使用三個變量，ones twos xthree，如果二進制表示中，某個數(shù)位上"1"出現(xiàn)一次，那么ones在這個數(shù)位上就是"1"，同理twos表示出現(xiàn)兩次。
- 看看ones twos 的變化規(guī)則。新進來一個數(shù)nums[i]，考察ones&nums[i],如果ones在這個比特位上為1，表面之前這個比特位"1"出現(xiàn)過一次，現(xiàn)在nums[i]在這個比特位上又為1，那么自然就是出現(xiàn)了兩次"1"，所以twos在這個比特位上就應該為1。ones的變化規(guī)則很簡單，異或就行了。需要注意的是如果某個比特位在ones和twos中都為1,那么就代表出現(xiàn)了三次，需要把這個比特位清零。
- 遍歷結(jié)束后，ones就是出現(xiàn)一次的數(shù)，twos就是出現(xiàn)兩次的數(shù)。
算法原理
從比特位來考慮，出現(xiàn)三次的數(shù)在遍歷結(jié)束之后對ones和twos都沒有影響，因為他們最后會在他們比特位表示為"1"的位置上出現(xiàn)三次，他們的影響被代碼
xthree = ~(ones & twos);
ones&=xthree;
twos&=xthree;
抹去，最后ones的各個比特位就是只出現(xiàn)一次的那個數(shù)的比特位，twos的各個比特位就是只出現(xiàn)兩次的那個數(shù)的比特位。
算法代碼
public class Solution {
public int singleNumber(int[] nums) {
//2,2,3,2
int ones=0;//二進制表示中“1”出現(xiàn)一次的數(shù)位
int twos=0;//二進制表示中“1”出現(xiàn)兩次的數(shù)位
int xthree=0;
for(int i=0;i<nums.length;i++){
twos|=(ones&nums[i]);//出現(xiàn)兩次，當然是“之前”位置上首先就是“1”（ones），然后輸入的數(shù)樹在這個位置上又是“1”
ones^=nums[i];//出現(xiàn)一次，當然是異或就行了，這樣出現(xiàn)一次的變?yōu)?，出現(xiàn)0次的變?yōu)?
xthree = ~(ones & twos);//一個數(shù)位在ones和twos同時為1，表示當前數(shù)位出現(xiàn)了3次，應該把這個數(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]
位操作方法三
這個方法其實和方法二一樣，只不過搞得有點像數(shù)電設計中的狀態(tài)轉(zhuǎn)移。
算法步驟&原理
a表示32位的int，a的每一位怎么確定，在遍歷原數(shù)組過程中，考察原數(shù)組中數(shù)的比特位表示，如果該位上"1" 出現(xiàn)次數(shù)為2，那么該位就為1，否則為0
同理
a表示32位的int，b的每一位怎么確定，在遍歷原數(shù)組過程中，考察原數(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ù)為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;
}
}
當然，如果了解轉(zhuǎn)臺轉(zhuǎ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ù)組中有兩個不同的數(shù)都只出現(xiàn)過一次，其他數(shù)都出現(xiàn)兩次，讓找出這兩個數(shù)。
算法描述
- 對這些數(shù)進行異或操作得到ones
- 移位與操作得到once的比特位表示的第一個非“0”位置，并把一個數(shù)賦值為僅該位置為1，其他位置為0
- 用這個數(shù)去和數(shù)組中的數(shù)做與運算，根據(jù)與運算結(jié)果是否為0可以把原數(shù)組中的數(shù)分為兩個陣營，分別對兩個陣營進行異或操作，最終得到的兩個結(jié)果就是所求的兩個數(shù)。
算法原理
有兩個數(shù)a,b只出現(xiàn)一次，其他兩次，那么所有數(shù)進行異或之后的結(jié)果ones，ones比特位表示為1的位置肯定就是a和b在這個位置為一個1一個0，那么就可以使用這個位置把a和b分到不同的陣營中，兩個陣營都是包含a/b和一堆成對出現(xiàn)的數(shù)，對他們進行異或操作即可求出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;
}
}
當然了，繼續(xù)拓展的話，如果有兩個數(shù)出現(xiàn)1次，其他書出現(xiàn)三次，那么就是拓展一中的方法先找到為出現(xiàn)次數(shù)為1的兩個數(shù)共同影響產(chǎn)生的結(jié)果ones,然后找到一個為“1”的比特位，然后分陣營，就變?yōu)閮蓚€拓展一類型的問題。
如果一個一次一個兩次其他三次，那么一次的就是ones,兩次的就是twos。
