LeetCode136. 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

1

hash table

O(1)time O(n)space

先将所有数字存入hash table,key是数字,value是数字的个数。

1
2
3
4
5
6
7
int singleNumber(vector<int>& nums) {
unordered_map<int, int> m;
for (int i = 0; i<nums.size(); i++)
++m[nums[i]];
for (int i = 0; i<nums.size(); i++)
if (m[nums[i]] == 1) return nums[i];
return 0;

Bit manipulation

因为^运算具有交换律,且^运算同一个数结果为0,所以将所有数累计异或就可以得到只出现一次的数。

1
2
3
4
5
int singleNumber(vector<int>& nums) {
int ret=0;
for(auto num:nums) ret^=num;
return ret;
}
Thanks for Support.