Leetcode 136. single number

题目链接：https://leetcode.com/problems/single-number/

题目描述：

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：一开始只想到用map计数，value值累加到2就删掉这个元素，最后剩下的元素的key值即为所求。(这种方法就是hash table???!!）

class Solution { public: int singleNumber(vector<int>& nums) { map<int,int> count; for(int i=0;i<nums.size();i++) { count[nums[i]]++; if(count[nums[i]]==2) count.erase(nums[i]); } map<int,int>::iterator map_it=count.begin(); return map_it->first; } };思路2：用异或运算，好神奇，，，，用异或运算的性质：结合律，交换律，自反性，将所有元素异或，最后剩下的元素即为所求

class Solution { public: int singleNumber(vector<int>& nums) { int length = nums.size(); int result = 0 ; for (int i=0; i<length; i++) { result ^= nums[i]; } return result; } }; 参考链接： http://blog.csdn.net/lwfcgz/article/details/7432541