Leetcode-137-只出现一次的数字II

Leetcode-137-只出现一次的数字 II

题目描述

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

示例 1：

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

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

1 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

方法一：哈希表

• 可以使用哈希映射统计数组中每个元素的出现次数。对于哈希映射中的每个键值对，键表示一个元素，值表示其出现的次数。
• 在统计完成后，遍历哈希映射即可找出只出现一次的元素。

class Solution {
    public int singleNumber(int[] nums) {
        // 1. 创建哈希表并把元素都放在内
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        for(int num : nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 2. 检查出现一次的数字并统计结果
        int ans = 0;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            int num = entry.getKey();
            int occ = entry.getValue();
            if(occ == 1){
                ans = num;
                break;
            }
        }
        return ans;
    }
}

复杂度分析：

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

方法二：二进制位

• 为了方便叙述，我们称「只出现了一次的元素」为「答案」。
• 由于数组中的元素都在 int（即 32位整数）范围内，因此我们可以依次计算答案的每一个二进制位是 0 还是 1。

---

• 具体地，考虑答案的第 i个二进制位（i 从 0 开始编号），它可能为 0 或 1。对于数组中非答案的元素，每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）。

• 因此：答案的第 i个二进制位就是数组中所有元素的第 i个二进制位之和除以 3 的余数。

• 这样一来，对于数组中的每一个元素x，使用位运算(x >> i) & 1 得到 x的第i个二进制位，并将他们相加再对3取余，得到的结果一定为0或者1，即答案的第i个二进制位

注意：

• 需要注意的是，如果使用的语言对「有符号整数类型」和「无符号整数类型」没有区分，那么可能会得到错误的答案。
  • 这是因为「有符号整数类型」(int 类型)的第31个二进制位补码对应的是符号位对应着 -2^{31}
  • 而「无符号整数类型」由于没有符号，第 31 个二进制位对应着 2^{31}
  • 因此在某些语言（Python）中需要对最高位进行特殊判断。

class Solution {
    public int singleNumber(int[] nums) {
        // 1. 初始化变量
        int ans = 0;

        // 2. 对32位依次进行二进制累和
        for(int i = 0;i < 32;++i){
            int total = 0;
            for(int num : nums){
                total += (num >> i) & 1;                    // (num >> i) & 1 拿到二进制位
            }

            // 3. 对累和进行求余数判断
            if(total % 3 != 0){
                ans |= (1 << i);                            // 说明ans这位应该取1                
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(nlogC)，其中 n 是数组的长度，C 是元素的数据范围，在本题中 logC=log2 32=32，也就是我们需要遍历第 0∼31 个二进制位。

• 空间复杂度：O(1)。

方法三： 数字电路

• 待后续

打赏