I title:
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
思路：异或
class Solution {
public:
int singleNumber(vector<int>& nums) {
int single = nums[];
for (int i = ;i < nums.size(); i++){
single ^= nums[i];
}
return single;
}
};
II
title：
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
思路：
这里我们需要重新思考，计算机是怎么存储数字的。考虑全部用二进制表示，如果我们把 第 ith 个位置上所有数字的和对3取余，那么只会有两个结果 0 或 1 (根据题意，3个0或3个1相加余数都为0). 因此取余的结果就是那个 “Single Number”.
一个直接的实现就是用大小为 32的数组来记录所有 位上的和。
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> v(,);
int result = ;
for (int i = ; i < ; i++){
for (int j = ;j < nums.size(); j++){
if ((nums[j] >> i) & )
v[i]++;
}
result |= ((v[i] % ) << i);
}
return result;
}
};
这个算法是有改进的空间的，可以使用掩码变量：
-
ones代表第ith 位只出现一次的掩码变量 -
twos代表第ith 位只出现两次次的掩码变量 -
threes代表第ith 位只出现三次的掩码变量
假设在数组的开头连续出现3次5，则变化如下：
ones =
twos =
threes =
--------------
ones =
twos =
threes =
--------------
ones =
twos =
threes =
--------------
当第 ith 位出现3次时，我们就 ones 和 twos 的第 ith 位设置为0. 最终的答案就是 ones。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one = , two = , three = ;
for (int i = ; i < nums.size(); i++){
two |= (one & nums[i]);
one ^= nums[i];
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
};