Single Number I
- 題目：有一個數(shù)據(jù)只出現(xiàn)一次藐翎，其他數(shù)據(jù)都出現(xiàn)兩次
- 思路：位運算（亦或）阔拳，只要循環(huán)異或齐邦，出現(xiàn)兩次的都變成0了析恋，最后只剩下出現(xiàn)一次的single number
- 異或解釋
- 按位異或運算符“^”是雙目運算符辉川。
- 功能是參與運算的兩數(shù)各對應(yīng)的二進位相異或祭椰。
- 當(dāng)兩個對應(yīng)的二進制位相異時蔓榄，結(jié)果為1
- 例如9^5 可寫成算式如下:00001001^00000101
- 結(jié)果為00001100 (十進制為12)
public class Solution {
public int singleNumber(int[] nums) {
int result=0;
for(int i=0;i<nums.length;i++){
result^=nums[i];
}
return result;
}
}
Single Number II
- 題目：有一個數(shù)據(jù)只出現(xiàn)一次详恼，其他數(shù)據(jù)均出現(xiàn)3次
- 思路：位運算
由于只有一個出現(xiàn)一次的數(shù)字堕战，其余數(shù)字都是出現(xiàn)三次
針對于序列中出現(xiàn)三次的所有數(shù)字的每一位來說坤溃，相加的結(jié)果只有兩種：1+1+1==3 或者0+0+0=0
所以加上只出現(xiàn)一次的數(shù)字的對應(yīng)位數(shù)字的話，結(jié)果有兩種：0或4
所以對上述的每一位求和之后對3取余践啄，結(jié)果為：1或0
當(dāng)結(jié)果為1的時候浇雹，也就是這個位上出現(xiàn)了只出現(xiàn)一次的數(shù)字
- 按位或運算
- 功能是參與運算的兩數(shù)各對應(yīng)的二進位相或。
- 只要對應(yīng)的二個二進位有一個為1時屿讽，結(jié)果位就為1昭灵。
- 例如：9|5可寫算式如下： 00001001|00000101
- 結(jié)果為：00001101 (十進制為13)
也就是9|5=13
public class Solution {
public int singleNumber(int[] nums) {
if(nums == null||nums.length == 0){
return -1;
}
//得到出現(xiàn)一次的數(shù)字的值
int result=0;
//int為4字節(jié)，那么共有32位
for(int i=0;i<32;i++){
//保存每一位求和值
int sum=0;
for(int j=0;j<nums.length;j++){
//累加所有數(shù)字上第i位的數(shù)字
sum+=(nums[j]>>i)&1;
//System.out.println("sum"+sum);
}
//取余得到第i位上的數(shù)字伐谈，更新result
result|=(sum%3)<<i;
//System.out.println("res+"+result);
}
return result;
}
}
Single Number III
- 題目：數(shù)組中只出現(xiàn)一次的兩個數(shù)字
- 思路：
- 異或思想烂完，一個數(shù)與自己異或為0，一個數(shù)與0異或為自己
- 由于其它數(shù)字兩兩相同诵棵，所以所有數(shù)異或則得到這兩個不同數(shù)的異或結(jié)果抠蚣。取這個結(jié)果的第一個1作為標(biāo)志位
- 這個標(biāo)志的1，必須是：這兩個數(shù)在該位一個為0履澳，一個為1嘶窄，因為是異或操作怀跛，結(jié)果為1必然在這里兩個數(shù)字一個為0一個為1
- 這里的結(jié)果必須是會產(chǎn)生的，也就是說肯定存在異或結(jié)果為1柄冲，不然這兩個數(shù)字就是相等的
- 這樣可以將數(shù)組分為兩組吻谋，一組在該標(biāo)志位為1，一組在該標(biāo)志位為0现横，這兩個不同數(shù)字分別在這兩組內(nèi)
- 將兩組內(nèi)的數(shù)分別異或漓拾，得到兩個結(jié)果則為這兩個不同的數(shù)
public class Solution {
public int[] singleNumber(int[] nums) {
int[] res=new int[2];
if(nums == null||nums.length == 0){
res[0]=0;
res[1]=0;
return res;
}
int sum=0;
for(int i=0;i<nums.length;i++){
sum^=nums[i];
}
int count=0;
while ((sum&1)==0){
sum>>=1;
count++;
}
res[0]=0;
res[1]=0;
for(int i=0;i<nums.length;i++){
if((nums[i]&(1<<count))==0){
res[0]^=nums[i];
}else{
res[1]^=nums[i];
}
}
return res;
}
}
