SingleNumber系列

SingleNumber_i_136

level：easy

题目

在一个全是int的数组中，有一个数字出现了一次，其他的数字都出现两次。

思路

根据算法符与非 两个相同的数字与非为0  0与某个数字与非还是本身

代码

class Solution {
    public int singleNumber(int[] nums) {
        int res=0;
        for(int i=0;i<nums.length;i++){
            res^=nums[i];
        }
        return res;
    }
}

SingleNumber_ii_137

level:Medium

题目

一个int数组中所有的数字都出现了三次，除了一个，找出出现一个的那个数字。

思路

int数字都是32位，每一位上出现三次的，找到其中只出现的不能整除3的位。最后算出结果。

代码

public int singleNumber_II(int[] nums){
    int ans = 0;
    for(int i=0;i<32;i++){
        int sum = 0;
        for(int j=0;j<nums.length;j++){
            if((nums[j]>>i&1)==1){
                sum++;
                sum%=3;
            }
        }
        if(sum!=0){
            ans |= (sum%3)<<i;
        }
    }
}

singleNumber_iii_260

level:Medium

题目

int数组中其他数字都出现了两次，只有两个数字出现了一次，找出这两个数字。

思路

因为第一个题目是只找到一个，而这个数组出现了两次，则想办法把他们两个分开。
至少有一位相与是不同的。所以以此为判断。

代码

public int[] singleNumber(int[] nums){
    int diff= 0;
    for(int num : nums){
        diff ^= num;
    }

    int[] res = {0,0};
    diff &= -diff;
    for(int i=0;i<nums.length;i++){
        if((nums[i]&diff)==0){
            res[0] ^= nums[i];
        }else{
            res[1] ^= nums[i];
        }
    }
    return res;
}