面试题56 - II. 数组中数字出现的次数 II

数组中数字出现的次数 II

题目描述

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

---

示例：

输入：nums = [3,4,3,3]
输出：4

输入：nums = [9,1,7,9,7,9,7]
输出：1

---

提示：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31

转载来源：力扣（LeetCode）

---

题目分析

这题目一开始是用哈希表来做的，步骤如下：

1. 如果数字不在哈希表里，put进去，value为1
2. 如果数字在哈希表里，且value为1，将其更新为2
3. 如果数字在哈希表里，且value为2，则将数字移除哈希表
4. 遍历完成后，哈希表KeySet里唯一的数字就是出现一次的数字

public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            if (hashMap.containsKey(num))
                if (hashMap.get(num) == 1)
                    hashMap.put(num, 2);
                else
                    hashMap.remove(num);
            else
                hashMap.put(num, 1);
        }
        return (int) hashMap.keySet().toArray()[0];
    }

提交上去之后发现击败了10%的用户，顿时呆了眼，怎么说也是O(N)的算法吧，怎么会这么差（可能是我吃Java不透，造成了过多的性能消耗）！

然后就想着之前做的这一题的easy版本，其他数字出现过两遍，然后根据两个相同数字的异或为0这个天才结论，将所有数字异或的结果返回回去，按道理说升级版的题目应该也能用位运算来做，就开始写写画画...

一个int型数有32位，分别有多少数字在第i位为1，例如【3 3 1 3】序列里，第一位为1的数字有4个，第二位为1的数字有3个，显然，因为第一位%3 != 0，那个唯一的数的第一位就是1，因为没人和它凑成三个1；而第二位%3 == 0，说明那一个唯一的数的第二位不为1；这样就很容易得到唯一的数32个位的具体情况！

public int singleNumber2(int[] nums) {
        int now = 1;
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int cnt = 0;
            for (int num : nums) {
                if ((num & now) != 0)
                    cnt++;
            }
            if (cnt % 3 == 1)
                ans |= now;
            now <<= 1;
        }
        return ans;
    }

强大的位运算时间复杂度也是O(N)，但是提交上去之后还是傻了眼，只击败58%的人，然后只能乖乖的看题解了；

题解里面有大牛用自动机的理论写了一个短小精悍的代码！感兴趣的可以去搜一下。
最让我不解的是，题解出现了排序方法，我对它进行了一些优化之后竟然击败了80%的用户（Java的内置排序已经优化到O(N)了？）

public int singleNumber3(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        Arrays.sort(nums);
        int index = 0;
        while (index < nums.length - 1) {
            if (nums[index] != nums[index + 1])
                return nums[index];
            index += 3;
        }
        return nums[nums.length - 1];
    }

代码文件

---

排序法
位运算法
哈希表法