LeetCode136 Single Number


描述

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

样例

1
2
Input: [1, 2, 3, 1, 2]
Output: 3

思路

给一个数组,其中只有一个数出现一次,其余数字都出现两次。现在要找出只出现过一次的那个数字是多少。

考虑异或运算的性质:两个相同的数异或为0 以及 异或满足交换律

那么我们只要对数组求个异或和 由于出现两次的数字都异或掉了,所以最后剩下的即为答案。

代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (auto& x : nums) {
ans ^= x;
}
return ans;
}
};