小米OJ002 找出单独的数字

描述

给出N个数字。其中仅有一个数字出现过一次,其他数字均出现过两次,找出这个出现且只出现过一次的数字。要求时间和空间复杂度最小。 ### 输入

输入多个数字,每个数字以空格分开。数字数量 N < 20,输入数字的最大值小于 256.

输出

输出内容为只出现过唯一一次的数字

输入样例

1
10 10 11 12 12 11 16

输出样例

1
16

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>

using namespace std;

int main()
{
int num, res = 0;
while (cin >> num) {
res ^= num;
}
cout << res << endl;
return 0;
}

思路

题目中明确说出只有一个数字出现过一次,其他数字均出现过两次,这时考虑到“异或”运算,当两个数相同时,异或为 0,而 0 与任何数异或仍然是那个数。当然,若无其他数字仅出现两次的限制,则可以考虑用 map 映射的方式存储数据,最后数个个数为 1 的那一元素。

# XiaoMi

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×