260. 只出现一次的数字 III(剑指 Offer 56 -I)
知识点：位运算
题目描述
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
示例
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。
输入：nums = [-1,0]
输出：[-1,0]
输入：nums = [0,1]
输出：[1,0]
解法一：位运算
这个题是LeetCode 136的升级，从一个元素变成了两个元素，所以我们可以采用分组的方法来解决，那么在每个组上再采用和136题一样的思路按位异或就可以了，分组的关键在于两点：
- 1.两个只有一个的分在不同组；
- 2.重复的数字要在一个组；
所以问题的关键就在于如何分组：将整个数组异或一遍后的结果其实就是那两个数字的异或结果，然后可以看这两个异或后的结果哪一位是1，是1的话就证明这两个数在这位上是不等的，那就可以根据这位进行分组，就能满足以上两个条件； - 1 两个相同的数字对应位是相等的，一定被分到一组里；
- 2 两个只有一个的数字在这位一个是1，一个是0，肯定被分到不同组里；
整体流程如下图：
class Solution {
public int[] singleNumber(int[] nums) {
int n = 0; //计算整个数组异或后的结果；
int m = 1; //分组依据，看异或后结果在哪位上为1；
int x = 0; //第一组；
int y = 0; //第二组；
for(Integer i : nums){
n ^= i;
}
//n要是在第i位为0，证明两个数字在第i位上相同，与m进行与操作后为0
//n要是在第i位为1，证明两个数字在第i位上不同，与m进行与操作后为1
while((n & m) == 0){
m = m << 1; //找到n在哪位上为1；依次为依据分组；
}
for(Integer i : nums){
if((i & m) == 0) x ^= i; //第一组；
else y ^= i; //第二组；
}
return new int[]{x,y};
}
}
时间复杂度:O(N);
空间复杂度:O(N);