 时间 O(1) 空间解法)
LeetCode 136 只出现一次的数字用异或运算实现 O(n) 时间 O(1) 空间解法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读LeetCode 136「只出现一次的数字」Single Number是一道经典位运算入门题给定一个非空整数数组除某个元素只出现一次外其余每个元素均出现两次要求在线性时间复杂度且不使用额外空间的前提下找出那个只出现一次的元素。本篇文章将以 leetcode 题解仓库中的 problems/136.single-number.md 为骨架完整讲解异或XOR运算的本质与规律、多语言实现JS/C/C/Java/Python、复杂度分析并延伸到两个只出现一次的数字LeetCode 260的分组异或解法最后梳理仓库中同主题的位运算题单帮助读者建立看到成对出现立即联想异或的思维模式。题目描述与约束分析原题problems/136.single-number.md给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。 说明 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗 示例 1: 输入: [2,2,1] 输出: 1 示例 2: 输入: [4,1,2,1,2] 输出: 4题目给出的两个硬性约束直接排除了两类最常见但不符合要求的解法不能使用排序排序的时间复杂度通常为 O(n log n)不满足线性时间 O(n) 的要求且排序后需要额外遍历定位落单元素。不能使用 map / hash 计数哈希表计数虽然可以达到 O(n) 时间但需要 O(n) 的额外空间违反空间复杂度 O(1) 的要求。因此符合 O(n) 时间 O(1) 空间的最自然工具就是按位异或XOR。仓库中的 thinkings/bit.md 也把 136、137、260、645 这四道题归为位运算套路专题136 正是这条套路线的第一题。前置知识异或运算的性质与规律要理解本题解法必须吃透异或的两个层面运算逻辑性质与组合规律。异或的运算性质两个数字异或的结果a ^ b是将 a 和 b 的二进制每一位逐位运算得出的数字运算逻辑是同一位数字相同同为 0 或同为 1→ 结果位为 0同一位数字不同一个 0 一个 1→ 结果位为 1。即相同为 0不同为 1。异或的三大规律任何数和本身异或则为 0a ^ a 0任何数和 0 异或是本身a ^ 0 a异或满足交换律与结合律a ^ b ^ c a ^ c ^ b (a ^ b) ^ c。前两条规律决定了偶数次出现的数字可以被抵消为 0第三条规律则保证无论数字在数组中以何种顺序排列抵消结果都相同。这正是thinkings/bit.md中反复强调的核心不要只背规律要理解二进制层面的本质否则很难在考场上主动联想到异或解法。核心思路全员异或成对抵消基于上述规律解法极其简洁用变量ret初始化为 0遍历数组对每个元素执行ret ret ^ nums[i]遍历结束后所有出现两次的元素都两两异或抵消为 0ret最终剩下的就是那个只出现一次的数字。以示例 2 为例手工推演[4,1,2,1,2]ret 0 ^ 4 4 ret 4 ^ 1 5 ret 5 ^ 2 7 ret 7 ^ 1 6 ret 6 ^ 2 4 ← 最终结果 41 ^ 1 0、2 ^ 2 0被抵消剩下的 4 就是答案。无论数组元素顺序如何交换律保证结果一致。从源码结构看仓库 SUMMARY.md 将本题编号为 0136 收录在题解目录中README.md 亦在精选题目中列出本题均归入位运算专题。多语言实现与完整代码原文档 problems/136.single-number.md 提供了 JS、C、C、Java、Python 五种语言的实现全部沿用初始化 0 循环异或这一模式JavaScript/** * param {number[]} nums * return {number} */ var singleNumber function (nums) { let ret 0; for (let index 0; index nums.length; index) { const element nums[index]; ret ret ^ element; } return ret; };Cint singleNumber(int* nums, int numsSize){ int res0; for(int i0;inumsSize;i) { res ^ nums[i]; } return res; }Cclass Solution { public: int singleNumber(vectorint nums) { auto ret 0; for (auto i : nums) ret ^ i; return ret; } }; // C one-liner利用标准库累积器 异或函数对象 class Solution { public: int singleNumber(vectorint nums) { return accumulate(nums.cbegin(), nums.cend(), 0, bit_xorint()); } };C 的 one-liner 变体使用了numeric头文件的accumulate与functional头文件的bit_xorint()把以 0 为初值、对全部元素做异或累积的意图表达得更加声明式。Javaclass Solution { public int singleNumber(int[] nums) { int res 0; for(int n:nums) { // 异或 res ^ n; } return res; } }Pythonclass Solution: def singleNumber(self, nums: List[int]) - int: single_number 0 for num in nums: single_number ^ num return single_number复杂度分析时间复杂度O(N)其中 N 为数组长度只需要一次线性遍历空间复杂度O(1)只使用了一个常数级变量ret/res/single_number与数组长度无关。这是位运算解法相对排序与哈希表方案的绝对优势所在也完整回应了题目不使用额外空间的进阶要求。延伸思考两个只出现一次的数字LeetCode 260原文档 problems/136.single-number.md 的延伸部分给出了同类问题的进阶版仓库 thinkings/bit.md 以260. 只出现一次的数字 3为题做了同样讲解有一个 n 个元素的数组除了两个数只出现一次外其余元素都出现两次找出这两个只出现一次的数要求时间复杂度 O(n)、开辟的内存空间固定与 n 无关。第一步全员异或得到两个独特数字的异或结果。沿用 136 的思路对全部元素做一次异或成对的元素全部抵消为 0剩下的ret a ^ b就是那两个只出现一次的数字的异或结果a ≠ b。第二步分组。由于a ≠ ba ^ b一定不为 0即二进制表示中至少有一位是 1。异或结果中某一位为 1意味着 a 与 b 在该位上必然不同一个为 0、一个为 1。以此位为依据分组两个独特的数字被分到不同组该位分别为 0 和 1所有出现两次的相同数字被分到同一组相同数字每一位都相同。于是两个组各自做一次全员异或就能分别得到 a 和 b。Python 实现来自 thinkings/bit.md 的singleNumbersclass Solution: def singleNumbers(self, nums: List[int]) - List[int]: ret 0 # 所有数字异或的结果 a 0 b 0 for n in nums: ret ^ n # 找到第一位不是0的 h 1 while(ret h 0): h 1 for n in nums: # 根据该位是否为0将其分为两组 if (h n 0): a ^ n else: b ^ n return [a, b]其中h从最低位1开始不断左移直到找到ret中第一个为 1 的位随后以h n 0为分界将数组分成两组并分别异或。整个过程仍然只有常数个额外变量空间复杂度保持 O(1)。仓库中的同主题扩展位运算题单本题并非孤立点。仓库以 thinkings/bit.md 为理论总纲串联了一系列位运算实战题阅读顺序上建议136成对抵消→ 260分组异或→ 137计数取模→ 645错误集合逐步加深对位运算套路的理解题号题目核心技巧136只出现一次的数字全员异或成对抵消137只出现一次的数字 II其他出现 3 次逐位统计 1 的个数对 3 取模260只出现一次的数字 III找异或结果中某一位 1 分组645错误的集合借用 260 的分组异或 索引数组191位 1 的个数n (n - 1)消除最后一位 1190颠倒二进制位按位提取与拼接1371每个元音包含偶数次的最长子字符串状态压缩 前缀异或1310子数组异或查询异或前缀和其中 problems/191.number-of-1-bits.md 同样将 位运算 列为前置知识并使用了另一个经典技巧n (n - 1)消除最后一位 1problems/1371.find-the-longest-substring-containing-vowels-in-even-counts.md 则将异或推广到奇偶性状态压缩 前缀和问题。这些题目共同构成了仓库位运算专题的完整闭环读者可对照 SUMMARY.md 中位运算章节逐题练习。小结LeetCode 136 的本质是考察异或运算在成对抵消场景下的应用由于a ^ a 0、a ^ 0 a且异或满足交换律与结合律一次 O(n) 遍历、O(1) 空间的全员异或即可精确找出唯一落单元素。掌握这一思维后同一套路可以无缝迁移到 260分组异或找两个数字、137计数取模等进阶问题是理解整个位运算体系的最佳起点。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
