O(n)
遍历每个数的每一位，统计每一位0和1的个数，累加乘积即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int totalHammingDistance(vector<int> &nums) {
int res = 0;
for (int i = 0, n = nums.size(); i < 32; i++) {
int cnt = 0;
for (int x : nums) {
cnt += (x >> i) & 1;
}
res += cnt * (n - cnt);
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int ret = 0;
int not_zero = 1;
while (not_zero) {
not_zero = 0;
int counter[2] = {0};
for (auto& num : nums) {
++counter[num & 1];
num >>= 1;
not_zero += (num != 0);
}
ret += (counter[0] * counter[1]);
}
return ret;
}
};
|