剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
2 <= nums.length <= 10000
解题思路
在 Easy | LeetCode 136. 只出现一次的数字 | 位运算 中, 只有一个数字出现一次, 其余出现两次的情况下, 直接异或所有值就解决了。那这里这样的数字有两个？直接异或的话, 最终的结果那就是这两个只出现了一次的那两个数字的异或值, 还是没办法解决问题, 那么怎么办呢？
解决方法很简单, 我把数字分成两组, 并且把这两个数字分别分到这两个数字当中。然后保证其他相同的数字一定分到同一个组, 问题就转化为为上一题的问题了。那么如何分组才能保证上述的要求呢？
-
首先我们根据异或的结果, 随便找一个哪两个数字的二进制表示里, 那个位数字不同的位。以这个不同的位为分组依据, 此位为0的分到1组, 此位为1的分到2组。这样分组问题就解决了。
-
然后在每个组内已经异或运算, 最终的得到的结果就是这两个数字
public int[] singleNumbers(int[] nums) {
int twoNumberXOR = 0;
// 先得到两个只出现的一次的数字的异或结果
for(int num : nums) {
twoNumberXOR ^= num;
}
// 根据异或结果找到不相同的位
int fisrtBitIs1 = findFisrtBitIs1(twoNumberXOR);
int number1 = 0;
int number2 = 0;
// 遍历数组所有数字
for (int num : nums) {
// 根据前面的那个位的值将其分组, 然后在分组内进行异或
if (((num >> fisrtBitIs1) & 1) == 1) {
number1 ^= num;
} else {
number2 ^= num;
}
}
// 最终每个分组的异或结果就是这两个只出现一次的数字
return new int[]{number1, number2};
}
public int findFisrtBitIs1(int num) {
int AND = 1;
int index = 0;
while((num & AND) == 0) {
AND = AND << 1;
index++;
}
return index;
}