这是一系列位运算的题目,本文将由浅入深,先从最简单的问题开始:
一个数组中只有一个数字出现过1次,其余数字都出现过两次,请找到那个只出现1次的数字。要求时间复杂度是 \(O(n)\),空间复杂度是 \(O(1)\)。
考虑到位运算中的异或运算,一个数字和它自己做异或,结果为0。所以只需要遍历整个数组,挨个异或,最后得到的结果就是那个只出现1次的数字。
class Solution { public: vector<int> singleNumbers(vector<int>& nums) { int res = 0; for (auto num : nums) { res ^= num; } return res; } };
一个整型数组
nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 \(O(n)\),空间复杂度是 \(O(1)\)。
与问题 1 的区别在于,这个问题中有两个出现次数为 1 的数字。可以将数组分成两个子数组,每个子数组中各含一个只出现 1 次的数字。具体做法为:
res
res
中的一个为 1 的数位,其余数位都变成 0,可以用 res & -res
保留最低位的 1,记为 div
div
做异或,按照结果为0或1分成2组,这样相同的数字都会被分到同一组,而那两个只出现 1 次的数字会被分到不同的组实际操作中不需要真正分组,只需要用两个变量 a
和 b
记录两个组的异或值即可。
class Solution { public: vector<int> singleNumbers(vector<int>& nums) { int res = 0; for (auto num : nums) { res ^= num; } int a = 0, b = 0; int div = res & -res; for (auto num : nums) { if (div & num) { a ^= num; } else { b ^= num; } } return {a, b}; } };
在一个数组
nums
中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
参考:K神的题解
如下图所示,考虑数字的二进制形式,对于出现三次的数字,各二进制位 出现的次数都是 3 的倍数。因此,统计所有数字的各二进制位中 1 的出现次数,并对 3 求余,结果则为只出现一次的数字。
class Solution { public: int singleNumber(vector<int>& nums) { vector<int> digit(32); // 记录所有数字每个数位上1出现的次数之和 for (auto num : nums) { // 遍历每个数字 for (int i = 0; i < 32; i++) { // 遍历每个数位 digit[i] += num & 1; // num & 1 得到该数位是否为1 num >>= 1; // 获得下一个数位 } } int ans = 0, m = 3; for (int i = 31; i >= 0; i--) { //倒着遍历digigt数组,因为高数位在大下标位置 ans <<= 1; // ans左移1位 ans |= digit[31 - i] % m; // 每个数位对m取余后再和ans做或运算 } return ans; } };
上面的代码只需要修改求余数值 \(m\) ,即可实现解决除了一个数字之外,其余数字都出现 \(m\) 次的通用问题。