136. Single Number

Given a **non-empty** 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?

**Example 1:**

1
2
Input: [2,2,1]
Output: 1
**Example 2:**
1
2
Input: [4,1,2,1,2]
Output: 4
思路:今晚有点累, copy~由于数字在计算机是以二进制存储的,每位上都是0或1,如果我们把两个相同的数字异或,0与0异或是0,1与1异或也是0,那么我们会得到0。根据这个特点,我们把数组中所有的数字都异或起来,则每对相同的数字都会得0,然后最后剩下来的数字就是那个只有1次的数字。这个方法确实很赞,但是感觉一般人不会忘异或上想,绝对是为CS专业的同学设计的好题呀,赞一个~~
1
2
3
4
5
6
7
8
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (auto num : nums) res ^= num;
return res;
}
};
Res. 8ms, 98.6%