剑指 Offer II 004. 只出现一次的数字 【模拟】【位数统计取余】

题目

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

难度：中等

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

题解

模拟

单纯模拟，使用Map存储次数，然后遍历找出只出现一次的元素

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(10);
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int res = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                res = entry.getKey();
                break;
            }
        }
        
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

位数统计取余（#）

int 类型固定为 32位。使用一个长度为 32 的数组 cnt[]cnt[] 记录下所有数值的每一位共出现了多少次 1，再对 cnt[]数组的每一位进行 mod 3操作，重新拼凑出只出现一次的数值。

mod取余，将多次出现的数都消除掉

class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < 32; j++) {
                if (((nums[i] >> j) & 1) == 1) {
                    count[j]++;
                }
            }
        }
        
        for (int i = 31; i >=0;i--) {
            count[i] = count[i] % 3;
            res = res << 1;
            if (count[i] == 1) {
                res = res | 1;
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)