1.题目描述
只出现一次的数字 III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
示例 1：
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。
示例 2：
输入：nums = [-1,0]
输出：[-1,0]
示例 3：
输入：nums = [0,1]
输出：[1,0]
2.思路
2.1 代码
由于所有数字中只有两个数（a和b）出现奇数次，其余数出现偶数次，那么将所有的数进行异或，则可以得到这两个出现奇数次的数异或结果 a ^ b。
假如 a ^ b 的结果为01101000，那么他与自己的相反（10011000）进行求或则可以得到该数右侧第一个1出现的位置（00001000），如下所示。当知道 a ^ b的右侧第一个数为1时，则a和b的该位置一定不同（异或不同为1相同为0）。那么再次遍历数组，并且数组中的数该位置为1的数进行异或运算，便可以得到a、b中的某一个数。
最后再用 a ^ b 的结果与得到的其中一个数进行异或运算，便可以得到另外一个数。
class Solution {
public int[] singleNumber(int[] nums) {
int eor = 0;
for (int i = 0; i < nums.length; i++) {
eor ^= nums[i];
}
int rightFirstOne = eor & (-eor);
int eorCheck = 0;
for (int i = 0; i < nums.length; i++) {
if ((nums[i] & rightFirstOne) != 0){
eorCheck ^= nums[i];
}
}
return new int[]{eorCheck, eor^eorCheck};
}
}
2.2 测试结果
通过测试
3.总结
- 数组中的所有数字依次异或可以得到出现奇数次的两个数异或结果
- 一个数异或自己的相反数，便可以得到该数右边第一次1出现的位置
- 通过第一次出现1的结果将原数组分成两拨，一拨该位置为1，另一拨该位置为0
- 通过该位置为1的数进行异或，便得到a、b中的一个数
- 最后通过 a ^ b ^ a = b 或者 a ^ b ^ b = a 得到另外一个数