尧图网站建设 
LeetCode-Book 详解 LCR 177「撞色搭配」异或分组找出两个只出现一次的数字Python / Java / C【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读「撞色搭配」LCR 177等价于《剑指 Offer 56 - I. 数组中数字出现的次数》是位运算经典题型给定一个整型数组sockets其中恰好有两个数字只出现一次其余数字均出现两次要求找出这两个数字。本文以 LCR 177. 撞色搭配 为核心骨架完整推导「全员异或 → 定位分界位 → 分组异或」的线性解法并结合仓库中 Python 解法、Java 解法、C 解法 三份可直接运行源码做对照验证。读完本文你将掌握异或运算的两个关键性质、如何用掩码m拆分数组以及本题在三种主流语言中的完整实现与运算优先级陷阱。一、题目约束为什么排除暴力法与哈希表本题对算法提出硬性要求时间复杂度 O(N)只能线性遍历数组空间复杂度 O(1)不允许使用哈希表、计数数组等额外存储。因此首先排除两类直觉方案暴力法两层循环两两比较时间复杂度 O(N²)不满足要求哈希表统计法虽然能降到 O(N) 时间但需要 O(N) 的哈希表空间不满足空间约束。在 O(N) 时间 O(1) 空间的约束下位运算异或成为唯一的自然解法。二、位运算基础异或的两个关键性质设整型数组sockets中出现一次的数字为x出现两次的数字为a, a, b, b, ...sockets [a, a, b, b, ..., x]异或运算^具有两个重要性质自反性归零律两个相同数字异或为 0即对任意整数a有a ⊕ a 0交换律与结合律a ⊕ b b ⊕ a且运算顺序不影响结果。因此若将sockets中所有数字依次执行异或出现两次的数字会两两抵消为 0留下的结果就是那个只出现一次的数字xa ⊕ a ⊕ b ⊕ b ⊕ ... ⊕ x 0 ⊕ 0 ⊕ ... ⊕ x x由于异或满足交换律以上结果与sockets的元素顺序无关。这就是「简化问题」——数组中除一个数字外其他数字都出现两次——的解法。三、本题难点两个只出现一次的数字「撞色搭配」的难点在于数组sockets中有两个只出现一次的数字设其为x、y因此无法通过一次全员异或直接得到这两个数字——全员异或的结果是x ⊕ y而非x或y本身。关键突破口在于由于x ≠ y则x和y的二进制表示中至少有一位不同一个为 0、一个为 1。根据这一位可以将sockets拆分为两个子数组分别包含x和y。拆分之后两个子数组都满足「除一个数字之外其他数字都出现了两次」因为成对出现的数字在同一个二进制位上取值相同必然被分到同一组。于是仿照第二节的简化问题思路分别对两个子数组遍历执行异或即可分别得到x和y。四、算法流程详解五步步骤 1遍历sockets执行全员异或设整型数组sockets [a, a, b, b, ..., x, y]对全部数字执行异或a ⊕ a ⊕ b ⊕ b ⊕ ... ⊕ x ⊕ y 0 ⊕ 0 ⊕ ... ⊕ x ⊕ y x ⊕ y得到的结果记为n原文档中写作z即n x ⊕ y。步骤 2循环左移计算掩码m根据异或运算的定义若整数x ⊕ y的某个二进制位为 1则说明x和y在这一位上取值不同一个 0、一个 1。找到x ⊕ y中任意一个为 1 的二进制位即可据此把数组拆成两个子数组。根据与运算的特点可以逐位判断某整数某一位是否为 1若a 0001 ≠ 0则a的第一位为 1若a 0010 ≠ 0则a的第二位为 1以此类推……因此初始化辅助变量m 1通过与运算从右向左循环判断找到x ⊕ y的第一个最低位的1 所在位置记录于m中while n m 0: # m 循环左移一位直到 n m ! 0 m 1while ((n m) 0) // m 循环左移一位直到 n m ! 0 m 1;while ((n m) 0) // m 循环左移一位直到 n m ! 0 m 1;易错点运算符优先级Python 中的优先级高于n m 0等价于(n m) 0写法合法但 Java / C 中的优先级高于n m 0会被解析为n (m 0)语义错误。因此 Java / C 实现必须显式加括号写成(n m) 0最终版本代码也正是这么处理的。步骤 3按掩码m拆分sockets为两个子数组对sockets中每个数字num判断num m若num m ! 0该位为 1划分至子数组 1包含x或y中的一个若num m 0该位为 0划分至子数组 2包含另一个。由于x、y在掩码位上的取值必然相反它们一定被分到不同的子数组而所有成对出现的数字在掩码位上取值相同必然被分到同一组。步骤 4分别遍历两个子数组执行异或在遍历分组的同时直接对两组分别累计异或即可得到两个只出现一次的数字for num in sockets: if num m: x ^ num # 若 num m ! 0划分至子数组 1执行遍历异或 else: y ^ num # 若 num m 0划分至子数组 2执行遍历异或 return x, y # 遍历异或完毕返回只出现一次的数字 x 和 yfor (int num : sockets) { if ((num m) ! 0) x ^ num; // 若 num m ! 0划分至子数组 1执行遍历异或 else y ^ num; // 若 num m 0划分至子数组 2执行遍历异或 } return new int[] {x, y}; // 遍历异或完毕返回只出现一次的数字 x 和 yfor (int num : sockets) { if (num m) x ^ num; // 若 num m ! 0划分至子数组 1执行遍历异或 else y ^ num; // 若 num m 0划分至子数组 2执行遍历异或 } return vectorint {x, y}; // 遍历异或完毕返回只出现一次的数字 x 和 y步骤 5返回值返回两个只出现一次的数字x、y即可。注意返回顺序不影响正确性题目只要求返回这两个数字的集合。五、复杂度分析时间复杂度 O(N)线性遍历sockets使用 O(N) 时间寻找掩码m时遍历x ⊕ y的二进制位最多 32 位int 类型视为常数时间 O(1)。总时间复杂度为 O(N)。空间复杂度 O(1)仅使用x、y、n、m四个辅助变量均为常数大小额外空间。六、三语言完整代码Pythonclass Solution: def sockCollocation(self, sockets: List[int]) - List[int]: x, y, n, m 0, 0, 0, 1 for num in sockets: # 1. 遍历异或 n ^ num while n m 0: # 2. 循环左移计算 m m 1 for num in sockets: # 3. 遍历 sockets 分组 if num m: x ^ num # 4. 当 num m ! 0 else: y ^ num # 4. 当 num m 0 return x, y # 5. 返回出现一次的数字Javaclass Solution { public int[] sockCollocation(int[] sockets) { int x 0, y 0, n 0, m 1; for (int num : sockets) // 1. 遍历异或 n ^ num; while ((n m) 0) // 2. 循环左移计算 m m 1; for (int num : sockets) { // 3. 遍历 sockets 分组 if ((num m) ! 0) x ^ num; // 4. 当 num m ! 0 else y ^ num; // 4. 当 num m 0 } return new int[] {x, y}; // 5. 返回出现一次的数字 } }Cclass Solution { public: vectorint sockCollocation(vectorint sockets) { int x 0, y 0, n 0, m 1; for (int num : sockets) // 1. 遍历异或 n ^ num; while ((n m) 0) // 2. 循环左移计算 m m 1; for (int num : sockets) { // 3. 遍历 sockets 分组 if (num m) x ^ num; // 4. 当 num m ! 0 else y ^ num; // 4. 当 num m 0 } return vectorint {x, y}; // 5. 返回出现一次的数字 } };七、仓库源码对照与运行验证本题与《剑指 Offer 56 - I. 数组中数字出现的次数》是同一道题的不同表述sockets对应原题的nums方法名sockCollocation对应singleNumbers。在 LeetCode-Book 仓库中该题的解法以三个语言版本存放于剑指 Offer 代码目录逻辑与上文完全一致Python 版sfo_56i_single_number_i_s1.pySolution.singleNumbers末尾附测试用例nums [4, 1, 4, 6]可直接运行输出应为(6, 1)Java 版sfo_56i_single_number_i_s1.javamain方法内置int[] nums {4, 1, 4, 6}测试用例通过Arrays.toString(res)打印结果C 版sfo_56i_single_number_i_s1.cppmain中构造vectorint nums {4, 1, 4, 6}调用PrintUtil::printVector输出结果。以测试用例[4, 1, 4, 6]手推一遍全流程可直观验证算法正确性全员异或4 ⊕ 1 ⊕ 4 ⊕ 6 1 ⊕ 6 7即n 7二进制0111找掩码m 1时n m 7 1 1 ≠ 0故m 1最低位即可区分1与6分组异或4偶数位 0与6110最低位 0进入一组得到4 ⊕ 6 2……等等这里需要说明4100与1001在最低位上不同6110与4在最低位上同为 0。分组结果为{1}与{4, 4, 6}分别异或得到1与6即两个只出现一次的数字。其中 Python / Java / C 三份实现均引用了各自语言的公共工具头文件Python 的 include 包、Java 的include.*、C 的 include.hpp便于在本地直接编译运行验证。八、总结与延伸「撞色搭配」是「数组中只有一个数字出现一次」问题的升级版核心思路可概括为三步全员异或利用a ⊕ a 0消除所有成对数字得到x ⊕ y定位分界位从低位到高位找到x ⊕ y中第一个为 1 的位生成掩码m分组异或按num m将数组拆成两组分别异或得到x与y。该解法的时间复杂度 O(N)、空间复杂度 O(1)是位运算技巧在数组问题中的典型应用。进一步地若数组中有三个只出现一次的数字即 LCR 178「训练计划 VI」/ 剑指 Offer 56 - II则需要借助「按位计数对 3 取余」的思路其思想同样基于位运算读者可以在 LCR 178. 训练计划 VI 和仓库中对应的 sfo_56ii 系列源码 中继续深入。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 详解 LCR 177「撞色搭配」：异或分组找出两个只出现一次的数字（Python / Java / C++）
LeetCode-Book 详解 LCR 177「撞色搭配」异或分组找出两个只出现一次的数字Python / Java / C【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读「撞色搭配」LCR 177等价于《剑指 Offer 56 - I. 数组中数字出现的次数》是位运算经典题型给定一个整型数组sockets其中恰好有两个数字只出现一次其余数字均出现两次要求找出这两个数字。本文以 LCR 177. 撞色搭配 为核心骨架完整推导「全员异或 → 定位分界位 → 分组异或」的线性解法并结合仓库中 Python 解法、Java 解法、C 解法 三份可直接运行源码做对照验证。读完本文你将掌握异或运算的两个关键性质、如何用掩码m拆分数组以及本题在三种主流语言中的完整实现与运算优先级陷阱。一、题目约束为什么排除暴力法与哈希表本题对算法提出硬性要求时间复杂度 O(N)只能线性遍历数组空间复杂度 O(1)不允许使用哈希表、计数数组等额外存储。因此首先排除两类直觉方案暴力法两层循环两两比较时间复杂度 O(N²)不满足要求哈希表统计法虽然能降到 O(N) 时间但需要 O(N) 的哈希表空间不满足空间约束。在 O(N) 时间 O(1) 空间的约束下位运算异或成为唯一的自然解法。二、位运算基础异或的两个关键性质设整型数组sockets中出现一次的数字为x出现两次的数字为a, a, b, b, ...sockets [a, a, b, b, ..., x]异或运算^具有两个重要性质自反性归零律两个相同数字异或为 0即对任意整数a有a ⊕ a 0交换律与结合律a ⊕ b b ⊕ a且运算顺序不影响结果。因此若将sockets中所有数字依次执行异或出现两次的数字会两两抵消为 0留下的结果就是那个只出现一次的数字xa ⊕ a ⊕ b ⊕ b ⊕ ... ⊕ x 0 ⊕ 0 ⊕ ... ⊕ x x由于异或满足交换律以上结果与sockets的元素顺序无关。这就是「简化问题」——数组中除一个数字外其他数字都出现两次——的解法。三、本题难点两个只出现一次的数字「撞色搭配」的难点在于数组sockets中有两个只出现一次的数字设其为x、y因此无法通过一次全员异或直接得到这两个数字——全员异或的结果是x ⊕ y而非x或y本身。关键突破口在于由于x ≠ y则x和y的二进制表示中至少有一位不同一个为 0、一个为 1。根据这一位可以将sockets拆分为两个子数组分别包含x和y。拆分之后两个子数组都满足「除一个数字之外其他数字都出现了两次」因为成对出现的数字在同一个二进制位上取值相同必然被分到同一组。于是仿照第二节的简化问题思路分别对两个子数组遍历执行异或即可分别得到x和y。四、算法流程详解五步步骤 1遍历sockets执行全员异或设整型数组sockets [a, a, b, b, ..., x, y]对全部数字执行异或a ⊕ a ⊕ b ⊕ b ⊕ ... ⊕ x ⊕ y 0 ⊕ 0 ⊕ ... ⊕ x ⊕ y x ⊕ y得到的结果记为n原文档中写作z即n x ⊕ y。步骤 2循环左移计算掩码m根据异或运算的定义若整数x ⊕ y的某个二进制位为 1则说明x和y在这一位上取值不同一个 0、一个 1。找到x ⊕ y中任意一个为 1 的二进制位即可据此把数组拆成两个子数组。根据与运算的特点可以逐位判断某整数某一位是否为 1若a 0001 ≠ 0则a的第一位为 1若a 0010 ≠ 0则a的第二位为 1以此类推……因此初始化辅助变量m 1通过与运算从右向左循环判断找到x ⊕ y的第一个最低位的1 所在位置记录于m中while n m 0: # m 循环左移一位直到 n m ! 0 m 1while ((n m) 0) // m 循环左移一位直到 n m ! 0 m 1;while ((n m) 0) // m 循环左移一位直到 n m ! 0 m 1;易错点运算符优先级Python 中的优先级高于n m 0等价于(n m) 0写法合法但 Java / C 中的优先级高于n m 0会被解析为n (m 0)语义错误。因此 Java / C 实现必须显式加括号写成(n m) 0最终版本代码也正是这么处理的。步骤 3按掩码m拆分sockets为两个子数组对sockets中每个数字num判断num m若num m ! 0该位为 1划分至子数组 1包含x或y中的一个若num m 0该位为 0划分至子数组 2包含另一个。由于x、y在掩码位上的取值必然相反它们一定被分到不同的子数组而所有成对出现的数字在掩码位上取值相同必然被分到同一组。步骤 4分别遍历两个子数组执行异或在遍历分组的同时直接对两组分别累计异或即可得到两个只出现一次的数字for num in sockets: if num m: x ^ num # 若 num m ! 0划分至子数组 1执行遍历异或 else: y ^ num # 若 num m 0划分至子数组 2执行遍历异或 return x, y # 遍历异或完毕返回只出现一次的数字 x 和 yfor (int num : sockets) { if ((num m) ! 0) x ^ num; // 若 num m ! 0划分至子数组 1执行遍历异或 else y ^ num; // 若 num m 0划分至子数组 2执行遍历异或 } return new int[] {x, y}; // 遍历异或完毕返回只出现一次的数字 x 和 yfor (int num : sockets) { if (num m) x ^ num; // 若 num m ! 0划分至子数组 1执行遍历异或 else y ^ num; // 若 num m 0划分至子数组 2执行遍历异或 } return vectorint {x, y}; // 遍历异或完毕返回只出现一次的数字 x 和 y步骤 5返回值返回两个只出现一次的数字x、y即可。注意返回顺序不影响正确性题目只要求返回这两个数字的集合。五、复杂度分析时间复杂度 O(N)线性遍历sockets使用 O(N) 时间寻找掩码m时遍历x ⊕ y的二进制位最多 32 位int 类型视为常数时间 O(1)。总时间复杂度为 O(N)。空间复杂度 O(1)仅使用x、y、n、m四个辅助变量均为常数大小额外空间。六、三语言完整代码Pythonclass Solution: def sockCollocation(self, sockets: List[int]) - List[int]: x, y, n, m 0, 0, 0, 1 for num in sockets: # 1. 遍历异或 n ^ num while n m 0: # 2. 循环左移计算 m m 1 for num in sockets: # 3. 遍历 sockets 分组 if num m: x ^ num # 4. 当 num m ! 0 else: y ^ num # 4. 当 num m 0 return x, y # 5. 返回出现一次的数字Javaclass Solution { public int[] sockCollocation(int[] sockets) { int x 0, y 0, n 0, m 1; for (int num : sockets) // 1. 遍历异或 n ^ num; while ((n m) 0) // 2. 循环左移计算 m m 1; for (int num : sockets) { // 3. 遍历 sockets 分组 if ((num m) ! 0) x ^ num; // 4. 当 num m ! 0 else y ^ num; // 4. 当 num m 0 } return new int[] {x, y}; // 5. 返回出现一次的数字 } }Cclass Solution { public: vectorint sockCollocation(vectorint sockets) { int x 0, y 0, n 0, m 1; for (int num : sockets) // 1. 遍历异或 n ^ num; while ((n m) 0) // 2. 循环左移计算 m m 1; for (int num : sockets) { // 3. 遍历 sockets 分组 if (num m) x ^ num; // 4. 当 num m ! 0 else y ^ num; // 4. 当 num m 0 } return vectorint {x, y}; // 5. 返回出现一次的数字 } };七、仓库源码对照与运行验证本题与《剑指 Offer 56 - I. 数组中数字出现的次数》是同一道题的不同表述sockets对应原题的nums方法名sockCollocation对应singleNumbers。在 LeetCode-Book 仓库中该题的解法以三个语言版本存放于剑指 Offer 代码目录逻辑与上文完全一致Python 版sfo_56i_single_number_i_s1.pySolution.singleNumbers末尾附测试用例nums [4, 1, 4, 6]可直接运行输出应为(6, 1)Java 版sfo_56i_single_number_i_s1.javamain方法内置int[] nums {4, 1, 4, 6}测试用例通过Arrays.toString(res)打印结果C 版sfo_56i_single_number_i_s1.cppmain中构造vectorint nums {4, 1, 4, 6}调用PrintUtil::printVector输出结果。以测试用例[4, 1, 4, 6]手推一遍全流程可直观验证算法正确性全员异或4 ⊕ 1 ⊕ 4 ⊕ 6 1 ⊕ 6 7即n 7二进制0111找掩码m 1时n m 7 1 1 ≠ 0故m 1最低位即可区分1与6分组异或4偶数位 0与6110最低位 0进入一组得到4 ⊕ 6 2……等等这里需要说明4100与1001在最低位上不同6110与4在最低位上同为 0。分组结果为{1}与{4, 4, 6}分别异或得到1与6即两个只出现一次的数字。其中 Python / Java / C 三份实现均引用了各自语言的公共工具头文件Python 的 include 包、Java 的include.*、C 的 include.hpp便于在本地直接编译运行验证。八、总结与延伸「撞色搭配」是「数组中只有一个数字出现一次」问题的升级版核心思路可概括为三步全员异或利用a ⊕ a 0消除所有成对数字得到x ⊕ y定位分界位从低位到高位找到x ⊕ y中第一个为 1 的位生成掩码m分组异或按num m将数组拆成两组分别异或得到x与y。该解法的时间复杂度 O(N)、空间复杂度 O(1)是位运算技巧在数组问题中的典型应用。进一步地若数组中有三个只出现一次的数字即 LCR 178「训练计划 VI」/ 剑指 Offer 56 - II则需要借助「按位计数对 3 取余」的思路其思想同样基于位运算读者可以在 LCR 178. 训练计划 VI 和仓库中对应的 sfo_56ii 系列源码 中继续深入。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考