LeetCode中“只出现一次的数字”题解
题目
136. 只出现一次的数字
难度 简单
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1示例 2:
输入: [4,1,2,1,2]
输出: 4题解
思考：
这题拿到手，第一反应是用hash表，没有思考细节，只是觉得hash表肯定是可以搞定的，但是空间复杂度是 O(n)O(n)，不满足题意。
接着开始思考，如何才能做到空间复杂度是 O(1)O(1) 呢？
心想，如果使用暴力破解法，每次从数组中取一个数，记为number，然后从剩下的数中查找，如果找不到，则number即为要找的那个数。这种解法时间复杂度是 O(n^2)O(n2)。
如何能把时间复杂度降到 O(n)O(n)，有两个突破点：
暴力解法做了很多重复的工作
要充分利用题目的已有信息
通过第二点，找到了一个很重要的信息：除了某个元素只出现一次以外，其余每个元素均出现两次——异或运算，异或运算会把出现两次的值异或为0剩下的即为唯一值与0异或，还是这个唯一值
方法一：暴力查找
两次循环，代码略
方法二：排序
使用快速排序，复杂度O(nlogn)
方法三：hashmap哈希表
class Solution {
public int singleNumber(int[] nums) {
// 创建hashmap，键为对应值在数组nums中出现的次数
HashMap<Integer, Integer> map = new HashMap<>();
// 遍历数组,存入hashmap
for (int i = 0; i < nums.length; i++) {
// 获取此值在hashmap中的次数
Integer count = map.get(nums[i]);
// 将count++，如果第一次出现，将count赋值为1
count = count == null ? 1 : ++count;
// 将其值及其对应出现次数存入hashmap中
map.put(nums[i], count);
}
// 遍历hashmap哈希表
for (Integer value : map.keySet()) {
// 如果出现次数为1，将对应值返回
Integer count = map.get(value);
if (count == 1) {
return value;
}
}
return -1; // can't find it.
}
}
复杂度分析：
时间复杂度：O(n)
空间复杂度：O(N)
方法四：异或运算
异或运算
运算法则：
a ^ b = b ^ a
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
d = a ^ b ^ c 可以推出 a = d ^ b ^ c.
a ^ b ^ a = b.
异或运算
1、异或是一个数学运算符。应用于逻辑运算。
2、例如：真异或假的结果是真，假异或真的结果也是真，真异或真的结果是假，假异或假的结果是假。就是说两个值相 异结果为真。n^0=n n^n=0，即任何数与0进行异或，为它本身，两个相同的数进行异或运算，会得到0。
一道有意思的题目：
很多成对出现数字保存在磁盘文件中，注意成对的数字不一定是相邻的，如2, 5,3, 4, 7,3, 4, 2,5……，由于意外有一个数字消失了，如何尽快的找到是哪个数字消失了？
思路：由于有一个数字消失了，那必定有一个数只出现一次而且其它数字都出现了偶数次。用搜索来做就没必要了，利用异或运算的两个特性，代码与此题类似，同一问题
##### 特性
1.自己与自己异或结果为0，
2.异或满足 交换律。class Solution {
public int singleNumber(int[] nums) {
// 初始化res 为 nums[0]
int res = nums[0];
// 遍历数组，依次进行异或运算，由于异或运算具有交换性，所以最后的结果即为出现一次的数与0异或
for(int i = 1; i < nums.length; i++){
res ^= nums[i];
}
// 返回此数
return res;
}
}复杂度分析
时间复杂度：O(N)
空间复杂度：O(1)
