num出现一次，其余元素出现两次

异或位运算。相同为0，不同为1

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }
}

num1出现一次，num2出现一次，其余元素出现两次

思路：找出两个数在位上的不同特征。肯定会有一位他们两的异或是1。用这个特征进行分组，之后再用上面一题的思路来进行异或就可以找出他们

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] singleNumber(int[] nums) {
        // 求所有数字异或和
        int sum = 0;
        for (int num : nums) {
            sum ^= num;
        }
        // 找异或和第一个为1的位
        int mask = 1;
        while ((sum & mask) == 0) {
            mask <<= 1;
        }
        // 以该位为依据分组异或
        int x = 0;
        int y = 0;
        for (int num : nums) {
            if ((num & mask) == 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }
}

num出现一次，其余元素出现三次

看图思路：

image-20220312143515350

1
2
3
4
5
6
7
8
9
10
11
func singleNumber(nums []int) int {
        res := 0
        for i:=0 ; i<32 ; i++{
            bit := 0
            for _,v := range nums{
                bit += ((v>>i) & 1)
            }
            res += (bit%3)<<i
        }
        return res
}