只出现一次的数字

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

1.暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int singleNumber(vector<int> &nums) {
        vector<int> ans = nums;
        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        for (int i = 0; i < ans.size(); ++i) {
            int count = 0;
            for (int j = 0; j < nums.size(); ++j) {
                if (nums[j] == ans[i]) count++;
                if (count > 1) break;
            }
            if (count == 1) return ans[i];
        }
        return -1;
    }
};

2.哈希法

哈希法：哈希映射统计数组中每个元素的出现次数，在统计完成后，遍历哈希映射即可找出只出现一次的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        unordered_map<int, int> unmap;
        for (int num : nums) unmap[num]++;
        pair<int, int> p;
        for (auto p: unmap) {
            if (p.second == 1) {
                ans = p.first;
                break;
            }
        }
        return ans;
    }
};

3.位运算

（1）核心思想：

依次确定每一个二进制位，进行二进制位运算

由于数组中的元素都在 int 范围内，数字对应的二进制长度为 32 位整数，因此我们可以依次计算答案的每一个二进制位是 0 还是 1，

  • 考虑答案的第 i 个二进制位（i 从 0 开始编号）, 它可能为 0 或 1 对于数组中非答案的元素，

  • 每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，

  • 无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）

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

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

image-20230423203131099

（2）细节处理：

如果使用的语言对有符号整数类型和无符号整数类型没有区分，那么可能会得到错误的答案。

  • 这是因为有符号整数类型（如int 类型）的第31个二进制位（即最高位）是补码意义下的符号位，对应着 -231 ，而无符号整数类型由于没有符号，第 31 个二进制位对应着 231
  • 因此在某些语言, 例如 Python中需要对最高位进行特殊判断。

二进制操作解释：

  • 求 $num$ 的第 $i$ 位数字：(num >> i) & 1

  • 1 << i：表示将二进制数 1 左移 $i$ 位，即将 1 的二进制表示向左移动 $i$ 位。例如，1 << 3 的结果是二进制数 1000，即十进制数 8。

  • |=：按位或赋值运算符，将左侧的操作数与右侧的操作数按位或，并将结果赋值给左侧的操作数。

    例如有一个变量 a 的值是 0x0F （二进制表示为 00001111），执行 a |= 0x80 语句后，a 的值将变为 0x8F （二进制表示为 10001111）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (int num: nums) sum += ((num >> i) & 1);
            if (sum % 3) ans |= (1 << i);
        }
        return ans;
    }
};

$$

$$

$$

$$

$$

$$

$$

$$

$$

$$

$$

$$