給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。

說明：

你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎？

示例 1:

輸入: [2,2,1]
輸出: 1
示例?2:

輸入: [4,1,2,1,2]
輸出: 4

思路：拿map，set，都不符合要求。

map：

class Solution {public int singleNumber(int[] nums) {Map<Integer, Integer> map = new HashMap<>();for (Integer i : nums) {Integer count = map.get(i);count = count == null ? 1 : ++count;map.put(i, count);}for (Integer i : map.keySet()) {Integer count = map.get(i);if (count == 1) {return i;}}return -1; // can't find it.}
}

我們知道什么數字和自己異或，都等于0.

什么數字和0異或，都等于它本身。

所以全部異或一遍，答案就是那個出現一次的數字。

class Solution {public int singleNumber(int[] nums) {int ans = 0;for(int i :nums)ans ^= i;return ans;}
}

?