欢迎阅读 欢迎来到「只出现一次的数字 II」题解之旅本文将带你从在一堆三胞胎数字里找出那个落单的这一直观场景出发深入理解按位统计 模 3的巧妙运用并掌握如何逐位统计二进制中 1 的个数来还原出只出现一次的那个数。在开始之前建议你先了解题目背景这是 LeetCode 137 题给定整数数组nums除某个元素只出现一次外其余每个元素都恰好出现三次找出那个只出现一次的元素。本质上每个二进制位上1 的个数必然满足三的倍数关系问题转化为逐位统计后按模 3 判别。明确学习目标掌握按位统计bit counting技术理解为什么sum % 3 1的位属于答案并熟练处理负数补码与1 31溢出等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [2,2,3,2]输出3nums [0,1,0,1,0,1,99]输出99。本文将从问题转化、逐位统计、模 3 判别、结果拼装到代码实现层层递进。即使你对位运算还不熟悉我们也会从每个比特位单独数一数落单的那位就是答案的位这一直觉出发让你轻松抓住核心思想——逐位统计模 3 余一即答案位。现在让我们一起按位清点找出那个只出现一次的数字吧 愿旖旎· 个人主页学习专栏《算法专栏》《LangChain学习》《贪心算法》钱塘江上潮信来今日方知我是我✨当前学习内容《位运算》一.题目137. 只出现一次的数字 II - 力扣LeetCode​二、算法分析一、问题分析前置分析题目要求找出数组中只出现一次的元素其余元素均恰好出现三次。关键约束元素可能为负数补码表示要求线性时间 O(1) 空间不能用哈希表虽然能做但非最优。核心思路异或对出现偶数次有效x^x0但对三次立即失效改用逐位独立分析——对每个二进制位统计1 的个数出现三次的数字贡献3 的倍数只出现一次的数字贡献 1故sum % 3 1的位就是答案的位。 例子为什么每位数 1 的个数能定位答案nums [2, 2, 3, 2]期待答案3。看第 1 位权值 2四个数的第 1 位分别是1, 1, 1, 1→1 的个数 44 % 3 1说明答案的该位是 1看第 0 位权值 1分别是0, 0, 1, 0→ 个数 11 % 3 1答案该位也是 1 → 拼出11二进制3✅。三个2在每位上都贡献了 3 个 1模 3 后归零只剩答案的贡献。二、算法策略按位统计 模 3 判别核心步骤初始化ret 0答案按位拼装。外层遍历 32 个二进制位i从 0 到 31int 共 32 位。统计该位 1 的个数遍历nums用(x i) 1取出第 i 位累加到sum。模 3 判别若sum % 3 1说明该位属于只出现一次的数ret | (1 i)置位。返回32 位全部处理完ret即答案。 示例nums [2, 2, 3, 2]二进制10, 10, 11, 10位 i各元素第 i 位sum1 的个数sum % 3操作ret00, 0, 1, 011ret | 10 1111, 1, 1, 141ret | 11 2320, 0, 0, 000不置位33~31全 000不置位3第 0、1 位模 3 余 1其余位为 0拼出二进制11 3✅与题目示例一致。三、正确性说明简单版本各位独立二进制各位互不影响可以逐位独立分析——把找数字分解为确定每一位是 0 还是 1这是位运算方案的基石。三倍数归零出现三次的元素在每一位上都贡献 3 个若该位为 1或 0 个若该位为 0因此每位 1 的总数 3k (答案该位 ? 1 : 0)模 3 后恰好剩下答案的贡献。判别精确sum % 3 1⇔ 该位有落单的 1 ⇔答案该位为 1sum % 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 032 位全 0之后逐位置位。边界防护负数用补码参与右移与与运算(x i) 1对负数的第 31 位同样能正确取到 11 31在 int 上是有符号溢出UB严谨写法应用1u i或ret | (unsigned)1 inums长度至少为 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(vectorint 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 题的关键分野。难点2sum % 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 中有符号右移是实现定义行为多数编译器做算术右移高位补符号位。对负数xx 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)在空间上最优且不依赖额外存储适合大规模数据。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨