高效查找数组中唯一单一出现的数字 - 位运算解法

高效查找数组中唯一单一出现的数字 - 位运算解法

这篇文章将介绍如何使用位运算高效地找到数组中唯一一个出现一次的数字。我们将分析C++代码示例，并解释其背后的逻辑和时间复杂度。

问题描述:

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现三次。找出那个只出现了一次的元素。

**代码示例 (C++):**c++class Solution {public: int singleNumber(vector& nums) { int ans = 0; for (int i = 0; i < 32; i++) { int NumFlag = 0; int total = 0; for (auto num : nums) { total += ((num >> i) & 1); if ((num >> i) == 0) NumFlag++; } if (NumFlag == nums.size()) break; if (total % 3) { ans |= (1 << i); } } return ans; }};

代码解析:

这段代码巧妙地利用了位运算的特性来解决问题。

1. 初始化: ans 变量用于存储最终结果，初始化为 0。2. 遍历每一位: 外层循环遍历整数的 32 位（int 类型）。3. 统计每位上 1 的个数: 内层循环遍历数组 nums 中的每个数字，统计第 i 位上 1 出现的次数（total）以及该位为 0 的数字个数（NumFlag）。4. 判断唯一数字: - 如果 NumFlag 等于数组长度，说明所有数字的第 i 位都为 0，该位不属于唯一数字，跳出循环。 - 如果 total 不是 3 的倍数，说明唯一数字的第 i 位为 1，使用位或操作 (ans |= (1 << i)) 将该位设置为 1。5. 返回结果: 最后返回 ans，即为数组中唯一出现一次的数字。

时间复杂度:

该算法的时间复杂度为 O(n)，其中 n 是数组中元素的个数。虽然代码中有嵌套循环，但外层循环的次数是固定的 (32 次)，因此时间复杂度仍然是线性的。

总结:

使用位运算可以高效地解决查找唯一出现一次的数字问题。该方法逻辑清晰，代码简洁，并且具有较好的时间复杂度，是解决此类问题的优秀方案。