LeetCode136 Single Number 只出现一次的数字

数字"/>

LeetCode136 Single Number 只出现一次的数字

1. problem description

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:
Input: [2,2,1]
Output: 1

Example 2:
Input: [4,1,2,1,2]
Output: 4

2. solution

2.1 solution1

使用hash table，线性时间复杂度，但是使用了额外的存储空间

class Solution {
public:int singleNumber(vector<int>& nums) {unordered_set<int> bucket;int result = 0;unordered_set<int>::const_iterator it;for (int i = 0; i < nums.size(); ++i) {it = bucket.find(nums.at(i));if (it == bucket.end()) {bucket.insert(nums.at(i));} else {bucket.erase(nums.at(i));}}result = *bucket.begin();return result;}
};

2.2 solution2

由于题目说其他数字只出现2次，结合相同数字异或为0的性质，以及异或的交换律性质，可有：
((2 ^ 2)^ (1 ^ 1) ^ (4 ^ 4) ^ (5)) => (0 ^ 0 ^ 0 ^ 5) => 5.

class Solution
{public:int singleNumber(vector<int>& nums){int result = 0;int len = nums.size();for (int i=0;i<len;i++){result = result^nums[i];}return result;}
};