剑指 Offer 56 - I 数组中数字出现的次数
概述
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
要求时间复杂度是O(n),空间复杂度是O(1)。
之前有一道类似的,只有一个数字出现了一次,其他都出现了两次,当时那道题是用异或求出来的。
暴力遍历
用一个 set 来记录有没有出现过。
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
set<int> s;
for (auto n : nums) {
if (s.count(n) != 0) {
s.erase(n);
} else {
s.insert(n);
}
}
vector<int> ans(s.begin(), s.end());
return ans;
}
};
可以看到上面的暴力遍历方法其实不针对两个数字,多个数字也是 okay 的,
显然我们可以利用两个数字这一点来进行优化。
异或分组
看了《剑指 Offer》,同样是先异或,得到一个非 0 的数,从中选出一个为 1 的 bit, 显然这两个数字在该 bit 是不同的,那么按照该 bit 的取值对所有数字分组,这两个数字必然被分开, 其他两两相同的数字自然被分到同一个组,之后对这两个组的数字分别 XOR 求得那两个数字。
实现的时候注意位运算的优先级较低,不放心的话就套括号好咯。
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int t = nums[0];
for (int i = 1; i < nums.size(); i ++) t ^= nums[i];
int n = 0;
while (t % 2 == 0) {
t = t >> 1;
n ++;
}
int a = 0, b = 0;
for (auto num : nums) {
if ((num >> n) % 2 == 0) {
a ^= num;
} else {
b ^= num;
}
}
return {a, b};
}
};
Links: sword-offer-56-1