数组中数字出现的次数
题目描述
一个整型数组 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
解法:
如果只有一个出现一次的数,把所有数字异或起来就可以得到结果。因为 n ^ n = 0
,0 ^ n = n
。因此出现两次的数,两者异或后结果为 0
,0 ^ n = n
,因此最终结果就是那个出现一次的数。
但是次数出现一次的数有两个,设为 a
和 b
,全部异或后得到的结果为 a^b
。
在 a^b
的结果中,假设二进制最低位为 1
,就说明 a
和 b
的最低位是不同的。为此,在异或的过程中,可以把最低位为 1
的异或在一次,为 0
的异或在一起。这样 a
和 b
不就分开了吗。
因此,第一步还是一样的,把全部数字异或起来,得到 a^b
,然后找到 a^b
中某个为 1
的位。而后再次遍历数组,根据情况把它们异或在一起。
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int a_xor_b = 0;
for(int n: nums){
a_xor_b ^= n;
}
int i = a_xor_b & (-a_xor_b);
int a = 0, b = 0;
for(int n: nums){
if(n & i){
a ^= n;
}else{
b ^= n;
}
}
return vector<int>{a, b};
}
};
上面的寻找 a_xor_b
中为 1
的位采用的方法很巧妙,a_xor_b & (-a_xor_b)
。
因为 -a
的二进制表示为 ~(a - 1)
。即,把 a 减去 1,然后整体取反。因此 a & (-a) = a & ~(a-1)
。
假设 a = 0b10 0100
,那么:
a = 0b10 0100
a-1 = 0b10 0011
~(a-1) = 0b01 1100 (-a)
a & (-a) = 0x00 0100
发现了吗, a & (-a)
一下子就能得到 a
中为 1
的最低那一位。