 时间 O(1) 空间解法)
LeetCode 136 题解只出现一次的数字Single Number——异或运算的 O(n) 时间 O(1) 空间解法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本指南以本仓库 problems/136.single-number.en.md中文版见 problems/136.single-number.md为核心系统讲解 LeetCode 136「只出现一次的数字」的位运算解法。该题是本仓库 thinkings/bit.md位运算专题中的第一道入门题读者学完后将掌握异或XOR的本质与运算律、如何在 O(n) 时间与 O(1) 空间内定位唯一元素并能够进一步理解 137、260、645 等同族位运算题的分组套路。题目概述与约束分析题目原描述如下给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。 说明 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗 示例 1: 输入: [2,2,1] 输出: 1 示例 2: 输入: [4,1,2,1,2] 输出: 4这道题的关键约束有两个它们直接决定了可行解法的范围时间复杂度必须是 O(n)这使得先排序再扫描的解法不可行排序本身至少是 O(n log n)空间复杂度必须为 O(1)这使得借助 HashMap / 哈希表统计频次的解法不可行额外空间为 O(n)。因此能同时满足两个约束的经典手段就是位运算中的异或XOR。前置知识异或的性质与运算律本仓库将「位运算」整理为独立专题见 thinkings/bit.md英文版 thinkings/bit.en.md136 正是该专题的开篇题。在做题之前需要先吃透异或的三条基础1. 异或的运算规则按位计算两个数字异或的结果a ^ b是对 a 和 b 的二进制每一位独立进行运算后得到的数字。运算逻辑是同一位上的数字相同则为 0不同则为 1。a 2 - 二进制 10 b 3 - 二进制 11 a ^ b - 二进制 01 12. 异或的两条核心规律任何数和本身异或则为0a ^ a 0任何数和 0 异或则是本身a ^ 0 a。3. 异或满足交换律与结合律thinkings/bit.md 中明确补充了交换律a ^ b ^ c a ^ c ^ b交换律与结合律是本题解法成立的根本前提——它保证了无论数组中元素以何种顺序排列全员异或的最终结果都相同。核心思路全员异或成对元素自我抵消根据异或规律a ^ a 0与a ^ 0 a将所有数字进行一次异或出现两次的数字会两两抵消为 0唯一出现一次的数字与 0 异或后保持不变即为所求。以示例 2 为例手动推演数组: [4, 1, 2, 1, 2] 4 ^ 1 ^ 2 ^ 1 ^ 2 4 ^ (1 ^ 1) ^ (2 ^ 2) // 利用交换律与结合律 4 ^ 0 ^ 0 4答案正是唯一出现一次的数字 4。理解这一点需要注意很多人只是记住了异或的规律却缺乏对其**本质按位相同为 0、不同为 1**的理解因此在面试中难以主动想到这条解法。解题时应当从位的视角出发成对元素在每一位上的 1 的个数都是偶数异或后该位归零而唯一元素贡献的 1 会完整保留下来。代码实现JS / C / C / Java / Python原文档 problems/136.single-number.en.md 提供了五种语言的实现全部采用「初始化 ret 为 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 res 0; for(int i 0; i numsSize; i) { res ^ nums[i]; } return res; }C普通版 函数式一行版class 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()); } };其中 one-liner 版本使用numeric头文件中的std::accumulate配合标准库仿函数bit_xorint()把以 0 为初始值、对全数组做异或折叠表达为一行适合展示对 STL 算法的熟悉度。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)$仅使用一个临时变量不随 N 增长。这一复杂度是本题两个硬约束下的最优结果也是异或方案相比排序O(n log n)与哈希表O(n) 空间的核心优势所在。延伸进阶两个只出现一次的数字LeetCode 260原文档的「Extension」一节给出了升级版数组中除了两个数只出现一次外其余元素均出现两次找出这两个数同样要求 O(n) 时间、与 n 无关的固定额外空间。该题对应 LeetCode 260其完整解法同样收录于 thinkings/bit.md。推导过程分三步第一步全员异或按 136 的思路先做一次全员异或得到的结果ret正是那两个唯一数字的异或值其余成对元素已全部抵消。第二步找到分组依据由于两个唯一数字不同ret一定不为 0即二进制中至少有一位是 1。根据异或同一位相同为 0、不同为 1的性质这一位正是两个唯一数字在该位上不同的标记。从ret中任取一个为 1 的位例如取最低的 1 位h 1 while (ret h 0): h 1第三步按该位分组并各自异或以这一位是 0 还是 1 为分界线将原数组分成两组。分组天然满足两个条件两个唯一的数字被分进不同组——它们在该位上必然一个为 0、一个为 1相同的数字被分进同一组——相同的数每一位都相同自然落在同一组。于是每组分别做一次全员异或即可各自得到其中一个唯一数字a 0 b 0 for n in nums: if (h n 0): a ^ n else: b ^ n return [a, b]复杂度分析与 136 相同时间 O(N)空间 O(1)。这道题是理解异或 按位分组套路的关键进阶题建议在掌握 136 之后立即练习。同族题型把位运算套路连成体系thinkings/bit.md 将 136、137、260、645 四道题串成一条位运算练习线除本题与 260 外另外两道为137. 只出现一次的数字 II除一个数字出现一次外其余均出现三次。解法从异或升级为逐位统计 1 的个数并对 3 取模——统计每一位上 1 出现的次数若cnt % 3 ! 0则唯一数字在该位为 1。该题还涉及一个有价值的语言细节Python 中若不做符号位处理测试用例[-2,-2,1,1,-3,1,-3,-3,-4,-2]会错误输出4294967292即2^32 - 4需要在结果大于2^31 - 1时减去2^32以还原负数详见 thinkings/bit.md。645. 错误的集合将数组nums与其索引数组idx拼接后输入 singleNumbers即 260 的解法得到唯二不同的两个数再遍历一次区分出缺失值与重复值从而在 O(1) 额外空间内解题。此外位运算专题还推荐了相关练习problems/190.reverse-bits.md颠倒二进制位与 problems/191.number-of-1-bits.md位 1 的个数可结合n (n - 1)消除末尾 1 的技巧。读完 136 后按此路径练习即可把异或、按位统计、按位分组三类位运算套路收入囊中。小结LeetCode 136 是一道一题看清异或本质的经典题约束条件O(n) 时间、O(1) 空间天然排除了排序与哈希表迫使解题者转向位运算。掌握a ^ a 0、a ^ 0 a与交换律之后一行循环即可求解而 260 的按位分组则是同一套规律的进阶应用。建议结合本仓库 thinkings/bit.md 把 136 → 260 → 137 → 645 这条位运算题链完整刷完形成可复用的解题套路。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 136 题解：只出现一次的数字（Single Number）——异或运算的 O(n) 时间 O(1) 空间解法
LeetCode 136 题解只出现一次的数字Single Number——异或运算的 O(n) 时间 O(1) 空间解法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本指南以本仓库 problems/136.single-number.en.md中文版见 problems/136.single-number.md为核心系统讲解 LeetCode 136「只出现一次的数字」的位运算解法。该题是本仓库 thinkings/bit.md位运算专题中的第一道入门题读者学完后将掌握异或XOR的本质与运算律、如何在 O(n) 时间与 O(1) 空间内定位唯一元素并能够进一步理解 137、260、645 等同族位运算题的分组套路。题目概述与约束分析题目原描述如下给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。 说明 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗 示例 1: 输入: [2,2,1] 输出: 1 示例 2: 输入: [4,1,2,1,2] 输出: 4这道题的关键约束有两个它们直接决定了可行解法的范围时间复杂度必须是 O(n)这使得先排序再扫描的解法不可行排序本身至少是 O(n log n)空间复杂度必须为 O(1)这使得借助 HashMap / 哈希表统计频次的解法不可行额外空间为 O(n)。因此能同时满足两个约束的经典手段就是位运算中的异或XOR。前置知识异或的性质与运算律本仓库将「位运算」整理为独立专题见 thinkings/bit.md英文版 thinkings/bit.en.md136 正是该专题的开篇题。在做题之前需要先吃透异或的三条基础1. 异或的运算规则按位计算两个数字异或的结果a ^ b是对 a 和 b 的二进制每一位独立进行运算后得到的数字。运算逻辑是同一位上的数字相同则为 0不同则为 1。a 2 - 二进制 10 b 3 - 二进制 11 a ^ b - 二进制 01 12. 异或的两条核心规律任何数和本身异或则为0a ^ a 0任何数和 0 异或则是本身a ^ 0 a。3. 异或满足交换律与结合律thinkings/bit.md 中明确补充了交换律a ^ b ^ c a ^ c ^ b交换律与结合律是本题解法成立的根本前提——它保证了无论数组中元素以何种顺序排列全员异或的最终结果都相同。核心思路全员异或成对元素自我抵消根据异或规律a ^ a 0与a ^ 0 a将所有数字进行一次异或出现两次的数字会两两抵消为 0唯一出现一次的数字与 0 异或后保持不变即为所求。以示例 2 为例手动推演数组: [4, 1, 2, 1, 2] 4 ^ 1 ^ 2 ^ 1 ^ 2 4 ^ (1 ^ 1) ^ (2 ^ 2) // 利用交换律与结合律 4 ^ 0 ^ 0 4答案正是唯一出现一次的数字 4。理解这一点需要注意很多人只是记住了异或的规律却缺乏对其**本质按位相同为 0、不同为 1**的理解因此在面试中难以主动想到这条解法。解题时应当从位的视角出发成对元素在每一位上的 1 的个数都是偶数异或后该位归零而唯一元素贡献的 1 会完整保留下来。代码实现JS / C / C / Java / Python原文档 problems/136.single-number.en.md 提供了五种语言的实现全部采用「初始化 ret 为 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 res 0; for(int i 0; i numsSize; i) { res ^ nums[i]; } return res; }C普通版 函数式一行版class 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()); } };其中 one-liner 版本使用numeric头文件中的std::accumulate配合标准库仿函数bit_xorint()把以 0 为初始值、对全数组做异或折叠表达为一行适合展示对 STL 算法的熟悉度。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)$仅使用一个临时变量不随 N 增长。这一复杂度是本题两个硬约束下的最优结果也是异或方案相比排序O(n log n)与哈希表O(n) 空间的核心优势所在。延伸进阶两个只出现一次的数字LeetCode 260原文档的「Extension」一节给出了升级版数组中除了两个数只出现一次外其余元素均出现两次找出这两个数同样要求 O(n) 时间、与 n 无关的固定额外空间。该题对应 LeetCode 260其完整解法同样收录于 thinkings/bit.md。推导过程分三步第一步全员异或按 136 的思路先做一次全员异或得到的结果ret正是那两个唯一数字的异或值其余成对元素已全部抵消。第二步找到分组依据由于两个唯一数字不同ret一定不为 0即二进制中至少有一位是 1。根据异或同一位相同为 0、不同为 1的性质这一位正是两个唯一数字在该位上不同的标记。从ret中任取一个为 1 的位例如取最低的 1 位h 1 while (ret h 0): h 1第三步按该位分组并各自异或以这一位是 0 还是 1 为分界线将原数组分成两组。分组天然满足两个条件两个唯一的数字被分进不同组——它们在该位上必然一个为 0、一个为 1相同的数字被分进同一组——相同的数每一位都相同自然落在同一组。于是每组分别做一次全员异或即可各自得到其中一个唯一数字a 0 b 0 for n in nums: if (h n 0): a ^ n else: b ^ n return [a, b]复杂度分析与 136 相同时间 O(N)空间 O(1)。这道题是理解异或 按位分组套路的关键进阶题建议在掌握 136 之后立即练习。同族题型把位运算套路连成体系thinkings/bit.md 将 136、137、260、645 四道题串成一条位运算练习线除本题与 260 外另外两道为137. 只出现一次的数字 II除一个数字出现一次外其余均出现三次。解法从异或升级为逐位统计 1 的个数并对 3 取模——统计每一位上 1 出现的次数若cnt % 3 ! 0则唯一数字在该位为 1。该题还涉及一个有价值的语言细节Python 中若不做符号位处理测试用例[-2,-2,1,1,-3,1,-3,-3,-4,-2]会错误输出4294967292即2^32 - 4需要在结果大于2^31 - 1时减去2^32以还原负数详见 thinkings/bit.md。645. 错误的集合将数组nums与其索引数组idx拼接后输入 singleNumbers即 260 的解法得到唯二不同的两个数再遍历一次区分出缺失值与重复值从而在 O(1) 额外空间内解题。此外位运算专题还推荐了相关练习problems/190.reverse-bits.md颠倒二进制位与 problems/191.number-of-1-bits.md位 1 的个数可结合n (n - 1)消除末尾 1 的技巧。读完 136 后按此路径练习即可把异或、按位统计、按位分组三类位运算套路收入囊中。小结LeetCode 136 是一道一题看清异或本质的经典题约束条件O(n) 时间、O(1) 空间天然排除了排序与哈希表迫使解题者转向位运算。掌握a ^ a 0、a ^ 0 a与交换律之后一行循环即可求解而 260 的按位分组则是同一套规律的进阶应用。建议结合本仓库 thinkings/bit.md 把 136 → 260 → 137 → 645 这条位运算题链完整刷完形成可复用的解题套路。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考