企业官网建设流程全解析

👋 欢迎阅读

🎯 欢迎来到「只出现一次的数字 II」题解之旅！本文将带你从"在一堆三胞胎数字里找出那个落单的"这一直观场景出发，深入理解按位统计 + 模 3的巧妙运用，并掌握如何逐位统计二进制中 1 的个数来还原出只出现一次的那个数。

在开始之前，建议你先：

• 了解题目背景：这是 LeetCode 137 题，给定整数数组nums，除某个元素只出现一次外，其余每个元素都恰好出现三次，找出那个只出现一次的元素。本质上，每个二进制位上"1 的个数"必然满足三的倍数关系，问题转化为逐位统计后按模 3 判别。

• 明确学习目标：掌握按位统计（bit counting）技术，理解为什么sum % 3 == 1的位属于答案，并熟练处理负数补码与1 << 31溢出等边界情况。

• 准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如nums = [2,2,3,2]输出3，nums = [0,1,0,1,0,1,99]输出99）。

本文将从问题转化、逐位统计、模 3 判别、结果拼装到代码实现，层层递进。即使你对位运算还不熟悉，我们也会从"每个比特位单独数一数，落单的那位就是答案的位"这一直觉出发，让你轻松抓住核心思想——逐位统计，模 3 余一即答案位。现在，让我们一起按位清点，找出那个只出现一次的数字吧！ 🔢🎯

🔥愿旖旎· 个人主页

📘学习专栏：《算法专栏》《LangChain学习》《贪心算法》

🌄钱塘江上潮信来，今日方知我是我

✨当前学习内容：《位运算》

一.题目

137. 只出现一次的数字 II - 力扣（LeetCode）

​

二、算法分析

一、问题分析（前置分析）

• 题目要求：找出数组中只出现一次的元素，其余元素均恰好出现三次。
• 关键约束：元素可能为负数（补码表示）；要求线性时间 + O(1) 空间；不能用哈希表（虽然能做，但非最优）。
• 核心思路：异或对"出现偶数次"有效（x^x=0），但对"三次"立即失效；改用逐位独立分析——对每个二进制位统计"1 的个数"，出现三次的数字贡献3 的倍数，只出现一次的数字贡献 1，故sum % 3 == 1的位就是答案的位。

📌 例子：为什么"每位数 1 的个数"能定位答案

nums = [2, 2, 3, 2]，期待答案3。看第 1 位（权值 2）：四个数的第 1 位分别是1, 1, 1, 1→1 的个数 = 4，4 % 3 = 1，说明答案的该位是 1；看第 0 位（权值 1）：分别是0, 0, 1, 0→ 个数 = 1，1 % 3 = 1，答案该位也是 1 → 拼出11（二进制）=3✅。三个2在每位上都贡献了 3 个 1，模 3 后归零，只剩答案的贡献。

二、算法策略（按位统计 + 模 3 判别）

核心步骤：

1. 初始化：ret = 0（答案按位拼装）。
2. 外层遍历 32 个二进制位：i从 0 到 31（int 共 32 位）。
3. 统计该位 1 的个数：遍历nums，用(x >> i) & 1取出第 i 位，累加到sum。
4. 模 3 判别：若sum % 3 == 1，说明该位属于只出现一次的数，ret |= (1 << i)置位。
5. 返回：32 位全部处理完，ret即答案。

📊 示例（nums = [2, 2, 3, 2]，二进制10, 10, 11, 10）：

第 0、1 位模 3 余 1，其余位为 0，拼出二进制11 = 3✅，与题目示例一致。

三、正确性说明（简单版本）

• 各位独立：二进制各位互不影响，可以逐位独立分析——把"找数字"分解为"确定每一位是 0 还是 1"，这是位运算方案的基石。
• 三倍数归零：出现三次的元素，在每一位上都贡献 3 个（若该位为 1）或 0 个（若该位为 0）；因此每位 1 的总数 =3k + (答案该位 ? 1 : 0)，模 3 后恰好剩下答案的贡献。
• 判别精确：sum % 3 == 1⇔ 该位有落单的 1 ⇔答案该位为 1；sum % 3 == 0⇔ 答案该位为 0。判据与答案位一一对应，不会错判。
• 按位拼装完整：32 位逐个确定后，ret |= (1 << i)把答案的每一位精确还原，最终得到完整整数（含负数）。

📌 例子：为什么第四个 2 不影响结论

nums = [2, 2, 3, 2]：第 1 位有 4 个 1（三个来自 2、一个来自 3）。其中三个2的贡献是3 × 1 = 3（三倍数），3的贡献是 1，总数 4 →4 % 3 = 1。无论出现三次的数字有多少个、是三胞胎还是六胞胎，它们在每位上的贡献永远是 3 的倍数，模 3 后必然归零——这就是"三倍数归零"的通用性。

四、实现细节（边界防护）

• 初始化：ret = 0（32 位全 0，之后逐位置位）。
• 边界防护：负数用补码参与右移与与运算，(x >> i) & 1对负数的第 31 位同样能正确取到 1；1 << 31在 int 上是有符号溢出（UB），严谨写法应用1u << i或ret |= (unsigned)1 << i；nums长度至少为 1，循环安全。
• 复杂度：时间 O(32n) = O(n)（外层 32 次 × 内层 n 次），空间 O(1)（仅常数个变量）。
• 关键操作：if ((x >> i) & 1) sum++;（统计第 i 位的 1 个数）、if (sum % 3 == 1) ret |= (1 << i);（模 3 判别 + 按位置位）。

📌 例子：负数如何被正确处理

nums = [-2, -2, 1, -2]，期待1。-2的补码是0xFFFFFFFE（第 0 位为 0、第 1~31 位全为 1）。第 0 位：0, 0, 1, 0→ sum = 1 →1 % 3 = 1→ 答案第 0 位为 1；第 1 位：1, 1, 0, 1→ sum = 3 →3 % 3 = 0→ 答案该位为 0。最终拼出1✅——补码让位统计自动涵盖负数，无需任何符号特判。

五、返回值（目标映射）

• 返回ret：只出现一次的那个数字（含负数情形），对应题目"找出只出现一次的元素"。

三.代码

class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; // 答案：按位拼装 // 1. 逐位分析：int 共 32 位，每位独立统计 for (int i = 0; i < 32; i++) { int sum = 0; // 统计所有元素在第 i 位上“1”的个数 // 2. 取出每个元素的第 i 位并累加 for (const auto& x : nums) { if ((x >> i) & 1) { sum++; } } // 3. 模 3 判别：余 1 说明该位属于只出现一次的数 if (sum % 3 == 1) { ret |= (1 << i); // 把答案的第 i 位置 1 } } return ret; // 4. 返回拼装完成的答案 } };

四、易错点分析

难点1：为什么异或法在本题失效

// 136 题（其余出现两次）：ret ^= x 直接得出答案 // 本题（其余出现三次）：异或会得到 三个相同数的异或 = x，无法归零

异或的自消性质是x ^ x = 0（偶数次抵消）。本题其余元素出现三次（奇数次），x ^ x ^ x = x，无法抵消，异或会残留下污染项。因此必须改用逐位统计——按位"数 1 的个数"对任意出现次数都成立（模 3、模 5 均可扩展），这是本题与 136 题的关键分野。

难点2：sum % 3 == 1的数学依据

if (sum % 3 == 1) ret |= (1 << i);

第 i 位 1 的总数 =3 × (出现三次的元素中该位为 1 的个数) + (答案该位是 1 ? 1 : 0)。前半部分是3 的倍数，模 3 归零；故sum % 3恰好等于"答案该位是否为 1"。

难点3：(x >> i) & 1对负数的行为

if ((x >> i) & 1) // x 为负数时的右移

C++ 中有符号右移是实现定义行为（多数编译器做算术右移，高位补符号位）。对负数x，x >> i高位补 1，但& 1只取最低位，而我们关心的正是"第 i 位被移到最低位后的值"——因此& 1的结果仍然正确。若改用(x & (1 << i)) != 0的写法，同样正确且不依赖右移实现；理解"取位"两种写法的等价性，可避免被"负数右移"的说法误导。

五、流程图

🎯 闭幕

🎉 恭喜你完成了「只出现一次的数字 II」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。

💡深入思考

• 本题采用逐位统计 + 模 3的方法：对 int 的 32 位分别统计所有元素在该位上1 的个数，若某位的统计结果% 3 == 1，说明该位属于只出现一次的数。为什么这种逐位独立统计是可行的？位与位之间会相互干扰吗？

• 对于出现三次的数字，其每一位上的 1 都会贡献 3 个计数；而只出现一次的数字，其每一位上的 1 只贡献 1 个计数。因此模 3 后余数只可能是 0 或 1，为什么不可能出现 2？

📚延伸挑战

• 如果题目改为只有一个数字出现一次，其余数字都出现 k 次（k > 1），你如何用逐位统计的方法找到这个数字？请描述核心修改。

如果你觉得本文对你有所帮助，欢迎：

👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路

📌深入思考答案

• 逐位独立统计可行，因为整数的每一位在加法中互不影响，且模 3 运算可以分配到每一位上。位与位之间不会产生跨位干扰，因此可以分别处理 32 位。

• 模 3 余数只可能是 0 或 1：出现三次的数每位贡献 3 个 1（或 0），只出现一次的数每位贡献 1 个 1（或 0），所以总计数 = 3 * m + (0 或 1)，模 3 后只能是 0 或 1，不可能是 2。

🔍延伸挑战答案

• 挑战1：若其余数字出现 k 次，只需将判断条件从sum % 3 == 1改为sum % k == 1，其余逐位统计逻辑完全不变，即可找到只出现一次的数。时间 O(32n)=O(n)、空间 O(1)，在空间上最优，且不依赖额外存储，适合大规模数据。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨