leetcode 22.8.5 只出现一次的数字

只出现一次的数字

只出现一次的数字 - 只出现一次的数字 - 力扣（LeetCode）

HashMap

看到这题，首先想到的是可不可以设计一个特殊的三进制异或规则，但转头一想或许hashmap实现起来更简单。

public static int singleNumber(int[] nums) {
    //创建一个hashmap
    Map<Integer,Integer> map = new HashMap<>();
    for (int num : nums) {
        //这里用getOrDefault方法，取的时候可以给没有的键值对给个默认值
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    //遍历键值对，如果出现次数为1，也就是value为1，则返回
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (entry.getValue()==1) return entry.getKey();
    }
    //为了编译通过，默认返回个0;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

因为hashmap的查询时间复杂度为O(1)嘛，这样就可以让整个算法时间复杂度做到O(N)，但空间复杂度还是O(N)

按位运算

因为整数每个位上不是1就是0，如果把nums中所有数的某一位全部加起来，除以3，那么剩下的就是只出现一次的数的那个位上的数。只需要做32次就可以了

public static int singleNumber02(int[] nums){
    //先定义一个ans,作为初始化的答案
    int ans = 0;
    //因为整数是用32位二进制数储存的，我们按照位进行运算，那么就是循环32次
    for (int i = 0; i < 32; ++i) {
        int total = 0;
        for (int num: nums) {
            total += ((num >> i) & 1);
        }
        if (total % 3 != 0) {
            ans |= (1 << i);
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这个的时间复杂度为0(N),空间复杂度为O(1)