算法小知识----11.02----只出现过一次的数字
只出现一次的数字，大概有三道题，该题出自力扣的136题——只出现一次的数字（简单题）
1.只出现一次的数字I
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
审题
其实就是找出数组内只出现过一次的的target
有好几种方法：
hashMap，存储出现的值和次数
集合，若有相同的就remove，最后所剩的就是target
还是用集合，计算出所有元素的值的和；再计算所有元素的值的2倍的和，相减，就是target
但是由于空间复杂度有要求，所以可以使用异或的方法去实现
a ⊕ a = 0 ;
a ⊕ 0 = a ;
a ⊕ b ⊕ a = (a ⊕ a ) ⊕ b = 0 ⊕ b = b
异或：
刚好数组内是两个，所以异或后就是只出现过一次的数
编码
public int singleNumber(int[] nums) {
int single = 0;
for(int num: nums){
single ^= num;
}
return single;
}复制代码2.只出现一次的数字III
该题出自力扣的260题——只出现一次的数字III（中等题），题解经过自己消化
审题
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
这次经过简单题的进阶，多了一个数字，有两个元素只出现一次
本来也可以用HashMap的方式一把过的，但是由于有一个进阶的条件，空间复杂度要使用常量，这就意味着不能额外开辟一个hash去存储相应的值和次数
联想到简单题的解法，使用异或；但是简单题是只有一个数，根据异或的定理，最终的异或和就是只出现一次的数
哦豁~有了方向，找一个较为简单的方式去找到这个数： x & ( - x ) —— 找到二进制中最低那一位
遍历数组，分为两组，该位为1的一组，反之另一组；这样就把这个问题分解成两道简单题了
最终两组内所剩即为目标值
在这里，如果重用简单题的方式，最终得到的就是两个只出现1次的值的异或和；这里假设是 a 和 b
换位思考，因为异或的定理 + 二进制只有1和0；所以只有两个数一个为1、一个为0，最终才能为1
编码
public static int[] singleNumber(int[] nums) {
int xorsum = 0;
for (int num : nums) {
xorsum ^= num;
}
// 防止溢出
int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
int type1 = 0, type2 = 0;
for (int num : nums) {
if ((num & lsb) != 0) {
type1 ^= num;
} else {
type2 ^= num;
}
}
return new int[]{type1, type2};
}复制代码
作者：Jayhaw_花
链接：https://juejin.cn/post/7025784863370248229