Single Number I
- 题目：有一个数据只出现一次，其他数据都出现两次
- 思路：位运算（亦或），只要循环异或，出现两次的都变成0了，最后只剩下出现一次的single number
- 异或解释
- 按位异或运算符“^”是双目运算符。
- 功能是参与运算的两数各对应的二进位相异或。
- 当两个对应的二进制位相异时，结果为1
- 例如9^5 可写成算式如下:00001001^00000101
- 结果为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
- 题目：有一个数据只出现一次，其他数据均出现3次
- 思路：位运算
由于只有一个出现一次的数字，其余数字都是出现三次
针对于序列中出现三次的所有数字的每一位来说，相加的结果只有两种：1+1+1==3 或者0+0+0=0
所以加上只出现一次的数字的对应位数字的话，结果有两种：0或4
所以对上述的每一位求和之后对3取余，结果为：1或0
当结果为1的时候，也就是这个位上出现了只出现一次的数字
- 按位或运算
- 功能是参与运算的两数各对应的二进位相或。
- 只要对应的二个二进位有一个为1时，结果位就为1。
- 例如：9|5可写算式如下： 00001001|00000101
- 结果为：00001101 (十进制为13)
也就是9|5=13
public class Solution {
public int singleNumber(int[] nums) {
if(nums == null||nums.length == 0){
return -1;
}
//得到出现一次的数字的值
int result=0;
//int为4字节，那么共有32位
for(int i=0;i<32;i++){
//保存每一位求和值
int sum=0;
for(int j=0;j<nums.length;j++){
//累加所有数字上第i位的数字
sum+=(nums[j]>>i)&1;
//System.out.println("sum"+sum);
}
//取余得到第i位上的数字，更新result
result|=(sum%3)<<i;
//System.out.println("res+"+result);
}
return result;
}
}
Single Number III
- 题目：数组中只出现一次的两个数字
- 思路：
- 异或思想，一个数与自己异或为0，一个数与0异或为自己
- 由于其它数字两两相同，所以所有数异或则得到这两个不同数的异或结果。取这个结果的第一个1作为标志位
- 这个标志的1，必须是：这两个数在该位一个为0，一个为1，因为是异或操作，结果为1必然在这里两个数字一个为0一个为1
- 这里的结果必须是会产生的，也就是说肯定存在异或结果为1，不然这两个数字就是相等的
- 这样可以将数组分为两组，一组在该标志位为1，一组在该标志位为0，这两个不同数字分别在这两组内
- 将两组内的数分别异或，得到两个结果则为这两个不同的数
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;
}
}
