做网站推广被骗/网络营销的发展趋势

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

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

方法一：
使用map存一下，然后遍历一下就可以了。

代码：

class Solution {public int singleNumber(int[] nums) {// mapMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {if (map.containsKey(nums[i])) map.put(nums[i], map.get(nums[i]) + 1);else map.put(nums[i], 1);}for (Integer i : map.keySet()) {if (map.get(i) == 1) return i;}return -1;}
}

时间复杂度：O(n)
空间复杂度：O(n)

方法二：
排序 + 双指针，因为题目说，其他所有的数字都出现两次，那么就可以使用双指针。

代码：

class Solution {public int singleNumber(int[] nums) {// 排序 + 双指针 看清题意 其余每个元素均出现两次Arrays.sort(nums);int l = 0, r = 1;while (r < nums.length) {if (nums[l] != nums[r]) return nums[l];l += 2;r += 2;}return nums[nums.length - 1];}
}

时间复杂度：O(nlgn) 排序消耗
空间复杂度：O(lgn) 排序消耗

方法三：
异或运算。
原理：异或运算支持交换律，且相同的数字异或运算结果为0，并且0和任意数异或结果为任意数，这样就可以得到那个唯一不重复的数字。

代码：

class Solution {public int singleNumber(int[] nums) {// 异或运算 不同取1 相同取0 任意值和0进行异或运算结果为任意值int res = nums[0];for (int i = 1; i < nums.length; i++) {res ^= nums[i];}return res;}
}

时间复杂度：O(n)
空间复杂度：O(1)