首页 > 其他 > 详细

找出只出现一次的两个数字

时间:2019-02-23 22:14:48      阅读:154      评论:0      收藏:0      [点我收藏+]

问题

有一个 n 个元素的数组,除了两个数只出现一次外,其余元素都出现两次,让你找出这两个只出现一次的数分别是几,要求时间复杂度为 O(n) 且空间复杂度为O(1)(与 n 无关)。

例如:

输入: [1,2,2,1,3,4] 
输出: [3,4]

 

解决方法

已知相同的两个数异或结果为0,在这里把所有元素都异或,那么得到的结果就是那两个只出现一次的元素异或的结果。

然后,因为这两个只出现一次的元素一定是不相同的,所以这两个元素的二进制形式肯定至少有某一位是不同的,即一个为 0 ,另一个为 1 ,现在需要找到这一位。

根据异或的性质 任何一个数字异或它自己都等于 0,所以前面得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。

再然后,以这一位是 1 还是 0 为标准,将数组的 n 个元素分成两部分。

  • 将这一位为 0 的所有元素做异或,得出的数就是只出现一次的数中的一个
  • 将这一位为 1 的所有元素做异或,得出的数就是只出现一次的数中的另一个。

这样就解出题目。忽略寻找不同位的过程,总共遍历数组三次,时间复杂度为O(n)

代码:
 1 #include<cstdio>
 2 using namespace std;
 3 
 4 const int maxn = 100000 + 10;
 5 int num[maxn];
 6 int n;
 7 
 8 int main()
 9 {
10     scanf("%d", &n);
11     int res = 0;                    //记录所有数的异或结果
12     for (int i = 0; i < n; i++)
13     {
14         scanf("%d", &num[i]);
15         res ^= num[i];
16     }
17     int pos;                        //记录“1”的位置
18     for(int i = 0;(1 << i) <= res;i++)
19         if (res & (1 << i)) { pos = i; break; }
20     int ans1 = 0, ans2 = 0;                    //记录两个结果
21     for (int i = 0; i < n; i++)
22     {
23         if (num[i] & (1 << pos))  ans1 ^= num[i];
24         else  ans2 ^= num[i];
25     }
26     printf("%d %d\n", ans1, ans2);
27     return 0;
28 }

 

 

参考链接:

1、https://www.zhihu.com/question/269288074/answer/574871689

2、https://www.cnblogs.com/hezhiyao/p/7539024.html

 
 

找出只出现一次的两个数字

原文:https://www.cnblogs.com/lfri/p/10424378.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!