Hot 100 --- 只出现一次的数字

本文概览本文讲解只出现一次的数字其余数字都出现两次异或运算满足 aa0、a0a 且可交换可结合把所有数字全异或一遍成对的互相抵消成 0剩下的就是答案。用二进制逐位演示抵消过程O(n) 时间、O(1) 空间一、题目二、题目分析1. 题目要求给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。进阶要求你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗示例 1nums [2, 2, 1]→ 1示例 2nums [4, 1, 2, 1, 2]→ 4示例 3nums [1]→ 12. 怎么想这题题目给出的条件里有个关键信息除了答案其他数字都是成对出现的。那最直观的思路就来了——怎么把成对的数字消掉、只留下那个落单的顺着这个想法有几条路可以走用哈希集合把出现过的数字记下来第一次遇到就放进去第二次遇到就说明它成对了从集合里删掉。最后集合里剩下的就是那个落单的。这条路好想但要多花 O(n) 的空间。排序之后两两比较成对的会挨在一起扫一遍就能找出落单的。这是 O(n log n)也没达到线性的要求。有没有一种运算天生就能让两个相同的数互相抵消有就是异或。它比前两条路都好因为既快又不需要额外空间。3. 需要解决哪几个问题问题一哈希集合和排序这两条路为什么达不到题目线性 不用额外空间的要求问题二核心异或为什么能让相同的数字互相抵消从二进制位上到底发生了什么问题三为什么把所有数字一股脑异或起来完全不管顺序也能得出正确答案三、方法一哈希集合O(n) 空间1. 思路概览publicintsingleNumber(int[]nums){SetIntegersetnewHashSet();for(intnum:nums){if(!set.add(num)){// add 返回 false 说明这个数已经在集合里了是对里的第二个set.remove(num);}}returnset.iterator().next();}思路简要说明进进出出第一次遇到某个数就放进去第二次遇到add返回false说明它成对了从集合里移走剩下的就是答案所有成对的都被移走了集合里只剩那个落单的时间复杂度 O(n)空间 O(n)不满足进阶要求用了 O(n) 的额外空间2. 思路详解这个思路就是拿集合模拟配对的过程。set.add(num)会返回一个布尔值放进去之前集合里没有这个数就返回true已经有了就返回false。所以第一次遇到4集合里没有 →add返回true→ 留着第二次遇到4集合里已经有了 →add返回false→ 说明这一对凑齐了两个一起消掉把4从集合里remove。以[4, 1, 2, 1, 2]为例遇到 4set [4] 遇到 1set [4, 1] 遇到 2set [4, 1, 2] 遇到 11 已存在 → set [4, 2] 遇到 22 已存在 → set [4] 返回 4 ✓逻辑很直白代价是那个集合占用了 O(n) 的空间——题目偏偏要求不使用额外空间。3. 复杂度分析时间复杂度 O(n)遍历一次哈希操作均摊 O(1)。空间复杂度 O(n)最坏情况下集合里存近 n 个数。四、方法二排序后两两比较O(n log n)1. 思路概览publicintsingleNumber(int[]nums){Arrays.sort(nums);for(inti0;i1nums.length;i2){if(nums[i]!nums[i1]){returnnums[i];}}returnnums[nums.length-1];}思路简要说明排序让成对的数字挨在一起排完之后相同的数一定相邻两两跳着扫每次看一对(nums[i], nums[i1])不相等说明nums[i]就是落单的扫完没找到说明落单的是最后一个元素时间复杂度 O(n log n)空间 O(1)不算排序本身的开销2. 思路详解排序会把相等的元素排到一起所以数组变成一对、一对……最后可能单一个的样子。于是从下标 0 开始每次跨两步看一对如果这一对相等说明这对配上了往后跳两步继续如果这一对不相等说明前一个数没有同伴——它就是答案。用[4, 1, 2, 1, 2]举例排序后是[1, 1, 2, 2, 4]i0nums[0]1 和 nums[1]1 相等 → 跳过 i2nums[2]2 和 nums[3]2 相等 → 跳过 i4i1 越界循环结束 → 返回最后一个 4 ✓这个方法空间省了但排序要 O(n log n)比线性的要求慢一截。3. 复杂度分析时间复杂度 O(n log n)排序占主要开销。空间复杂度 O(1)只用了下标变量。五、方法三异或O(n) 时间 O(1) 空间1. 思路概览publicintsingleNumber(int[]nums){intans0;for(intnum:nums){ans^num;}returnans;}思路简要说明一个变量一路异或到底ans从 0 开始把每个数都异或进去成对的自动抵消两个相同的数异或得 0等于没参与剩下的就是答案所有成对数字抵消完ans里留下的只有那个落单的时间复杂度 O(n)空间 O(1)2. 思路详解第一步解决为什么异或能抵消——先看异或在二进制位上的规则异或^是按位运算先把两个数都写成二进制再让它们一位对齐一位地算。因为是二进制每一位上只可能是 0 或 1 两种值两个位碰在一起一共也只有四种组合规则就两条相同得 00 ^ 0 0 1 ^ 1 0 不同得 10 ^ 1 1 1 ^ 0 1这里要特别注意上面式子里的 0 和 1 全都是二进制位bit上的值说的是这一位取 0 还是取 1不是十进制的数字 0 和 1。所以这四行的意思是把某一位上的两个 bit 做异或得到的结果 bit是 0 还是 1——两个 bit 相同结果 bit 就是 0两个 bit 不同结果 bit 就是 1。一句话记住“相同得 0不同得 1”。由此立刻能推出两个性质a ^ a 0 ← 两个一模一样的数每一位上的两个 bit 都相同逐位算出来都是 bit 0一位一位全是 0整个数就是 0 a ^ 0 a ← 每一位拿 bit 和 0 去比原来是 bit 1 的不同得 1原来是 bit 0 的相同得 0结果原样不动第一个性质正是我们想要的两个相同的数异或结果就是 0等于互相抵消没出现过。第二步把示例 2 拆成二进制看抵消过程拿nums [4, 1, 2, 1, 2]来先把每个数写成二进制4 1 0 0 1 0 0 1 2 0 1 0 1 0 0 1 2 0 1 0现在一位一列地竖着看每一位各自做异或位2 位1 位0 4 1 0 0 1 0 0 1 2 0 1 0 1 0 0 1 2 0 1 0 ------------------------ 结果 1 0 0 4逐位解释位 0这一列是0、1、0、1、0。两个1来自那两个1异或时1 ^ 1 0正好抵消最后剩 0。位 1这一列是0、0、1、0、1。两个1来自那两个2同样抵消剩 0。位 2这一列是1、0、0、0、0。只有4贡献了一个1没有谁能和它抵消于是留下 1。三位合起来1 0 0正是 4——那个落单的数。换一个角度把整个异或过程一步步算出来ans 初始 000 ans ^ 4 000 ^ 100 100 → 4 ans ^ 1 100 ^ 001 101 → 5 ans ^ 2 101 ^ 010 111 → 7 ans ^ 1 111 ^ 001 110 → 6 ans ^ 2 110 ^ 010 100 → 4 ✓中间几步的ans是 5、7、6看着毫无规律但那只是还没配上对的临时状态。等到把1和1、2和2都异或进去它们两两抵消最后只剩 4。这也说明一件事不需要关心中间过程是什么只要保证每个数字都被异或了一次成对的就会自己消掉。第三步解决为什么可以不管顺序异或满足交换律a ^ b b ^ a和结合律(a ^ b) ^ c a ^ (b ^ c)。原因从按位独立就能看出来异或的每一位各算各的不同位之间互不影响。而单独看某一位这一位上无非是一堆 0 和 11的个数是偶数就全抵消、是奇数就留一个 1——数一数就行跟谁先谁后毫无关系。所以整个数组可以看成所有数字一起异或怎么打乱顺序、怎么分组都行4 ^ 1 ^ 2 ^ 1 ^ 2 (1 ^ 1) ^ (2 ^ 2) ^ 4 ← 用交换律结合律把成对的挪到一起 0 ^ 0 ^ 4 4成对的都变成了 00 ^ 4 4a ^ 0 a答案就浮出来了。第四步代码细节intans0;// 从 0 开始因为 0 异或任何数都是那个数本身0 ^ x xfor(intnum:nums){ans^num;// 逐个异或进去}returnans;为什么初值是 00 ^ x x0 是异或运算的零元拿它起步不会影响结果。数组只有一个元素循环走一遍ans 0 ^ nums[0] nums[0]直接返回它自己符合预期。负数也没问题异或是补码上按位算的性质a ^ a 0、a ^ 0 a对负数一样成立。3. 复杂度分析时间复杂度 O(n)一次遍历每个数只做一次异或。空间复杂度 O(1)只用一个变量ans。六、总结方法时间空间是否满足进阶要求哈希集合O(n)O(n)否排序 两两比较O(n log n)O(1)否时间不够线性异或O(n)O(1)是这题的关键在于抓住其余元素都出现两次这个条件然后找到一种相同的两个数碰一起就消失的运算——异或正好就是a ^ a 0成对的自动抵消a ^ 0 a落单的不受影响可交换、可结合所以能无视顺序从头到尾一把梭。前两种方法都能算出答案但一个要多花空间、一个要多花时间异或同时把时间和空间都做到了最优而且代码只有三行。