一组带数字编号的球，其中有两个编号只出现了一次，把它们找出来

[编程题]一组带数字编号的球，其中有两个编号只出现了一次，把它们找出来

热度指数：2889 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

一组带数字编号的球里除了两个编号之外，其它的编号都出现了两次。
请写程序找出这两个只出现一次的编号。要求时间复杂度是O(n)，空间复杂度是O(1)。

输入描述:

整形数组
长度不超过1000000

输出描述:

输出数组中2个只出现了一次的数
先输出较小的数

示例1

输入

输出

1 6

备注:

可以考虑以以下代码作为模板，实现其中的getNumber()函数。

#include <bits/stdc++.h>
using namespace std;
int a[1000001];
void getNumber(const int a[], int n, int&num1, int&num2) {
//自行实现，要求时间O(n),空间O(1)。
}
int main(void) {
int n = 0;
while (~scanf("%d",&a[n+1])) ++n;
int p,q;
getNumber(a,n,p,q);
if (p>q) swap(p,q);
printf("%d %d\n",p,q);
return 0;
}

算法知识视频讲解

牛客题解官

发表于 2020-06-05 17:28:21

题解题目难度：较难知识点：位运算解题思路：在思考这道题是，首先想到的可能是按照数据的顺序，一个一个数比较，标记出只出现一次的数，输出这个数即可，但是这个过程的复杂度很高，复杂度为n^2。在考虑这道题时，我们可以先思考一个简单版本：一个数组只有一个数字只出现一次，其他的数字都出现了两次。怎么查出展开全文