Open guodongxiaren opened 4 years ago
只有一个出现一次的就全员异或就好了。但是有两个的话就比较麻烦了。
别怕,可以分组异或。
先全员异或一遍,剩下的值就是两个单词数异或的结果。
这个数中为1的bit肯定不会在两个数中同时为1!所以以此切入,对数组分组。 这位为1的异或,这位不为1的异或。分别选出两个数字。
这位任选一个是1的bit就好。选第一位貌似简单写。既从7推出4。按每个数&4==1 与否来分组。
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int res = 0;
for (int n: nums) {
res ^= n;
}
int a = 0;
int b = 0;
int i = 1;
while ((res & i) != i) {
i <<= 1;
}
for (int n: nums) {
if ((n & i) == 0) {
a ^= n;
} else {
b ^= n;
}
}
return {a, b};
}
};
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
示例 1:
示例 2:
限制:
2 <= nums <= 10000