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?
Subscribe to see which companies asked this question
class Solution { public: int singleNumber(vector<int>& nums) { sort(nums.begin(), nums.end()); for(int i = 1; i < nums.size() - 1; ++i) if(nums[i - 1] != nums[i] && nums[i] != nums[i + 1]) return nums[i]; return nums.size() == 0 ? 0 : nums[0]; //任意输出0或者第一个值 } };
class Solution { public: int singleNumber(vector<int>& nums) { map<int, int> m; for(int i = 0; i < nums.size(); ++i) ++m[nums[i]]; for(map<int, int>::iterator iter = m.begin(); iter != m.end(); ++iter) { if(iter->second == 1) return iter->first; } return nums.size() == 0 ? 0 : nums[0]; //任意输出0或者第一个值 } };
解法3：考虑题目要求的O(n)时间复杂度和O(1)空间复杂度，则不能使用常规排序法或者Map。题目的Hide Tags提示使用位操作。注意到两个相同的数异或后结果是0，因此如果数组中只有一个数只出现一次，而其他所有数都出现两次的话，整个数组的所有数异或之后得到的结果必定是那个单独的数。
class Solution { public: int singleNumber(vector<int>& nums) { int res = 0; for(int i = 0; i < nums.size(); ++i) res ^= nums[i]; return res; } };
原文：http://www.cnblogs.com/aprilcheny/p/4932505.html