LeetCode136 Single Number

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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;
}
};
分享到 评论