本文共 1503 字,大约阅读时间需要 5 分钟。
一个整型数组 nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O ( n ) O(n) O(n) ,空间复杂度是 O ( 1 ) O(1) O(1) 。
示例 1:
输入:nums = [4,1,4,6]输出:[1,6] 或 [6,1]
示例 2:
输入:nums = [1,2,10,4,1,4,3,3]输出:[2,10] 或 [10,2]
限制: 2 <= nums.length <= 10000
题意:这道题是一个数组只有一个数字出现了一次的拓展。那道题应用异或运算:任何一个数字异或自己都等于零。于是从头到尾异或数组中的每个数字,那么最后的结果刚好是那个只出现一次的数字,其他成对出现的数字都在异或中抵销了。
既然如何,我们试着将原数组分成两个子数组,让每个子数组中包含一个只出现一次的数字,而其他数字都成对出现两次。如果能够这样拆分两个数组,就可以沿用前面的方法,分别找出两个只出现一次的数字。
为此,依次异或数组中的每个数字,最后得到的肯定是两个只出现一次的数字的异或结果,因为其他数字都出现了两次,在异或中被抵消了。由于存在两个数字作为结果,它们肯定不一样,那么它们的异或值二进制表示中至少有一位为 1 1 1 。于是在结果数字中找到第一个为 1 1 1 的位的位置,记为第 k k k 位。注意:两个只出现一次的数字,它们在第 k k k 位肯定不同,于是可以作为区分。
现在以第 k k k 位是否为 1 1 1 为标准,将原数组中的数字分成两个数组——第一个数组中每个数字的第 k k k 位都是 1 1 1 ,第二个数组中的每个数字的第 k k k 位都是 0 0 0 。于是,出现了两次的数字肯定被分配到同一个子数组,因为两个相同的数字它们的任意一位都是相同的;而出现了一次的两个数字被分配到两个子数组中。此后,沿用之前的解法,就可以解决本问题了。
举例如 {2, 4, 3, 6, 3, 2, 5, 5}
,依次异或后得到的结果二进制表示是 0010
,于是倒数第二位是 1
。根据数字的倒数第二位进行划分,得到两个子数组: {2, 3, 6, 3, 2}
中所有数字的倒数第二位都是 1
;{4, 5, 5}
中所有数字的倒数第二位都是 0
。接下来分别异或就可以了。
代码如下:
class Solution { public: vector singleNumbers(vector & nums) { if (nums.size() == 2) return nums; int result = 0, first1 = 0; for (const int v : nums) result ^= v; while (!(result & 1)) { result >>= 1; ++first1; } vector ans(2, 0); for (const int v : nums) { if ((v >> first1) & 1) ans[0] ^= v; else ans[1] ^= v; } return ans; }};
转载地址:https://memcpy0.blog.csdn.net/article/details/108389063 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!