题目来源
求一堆数字之间的汉明码距离之和。
我一开始一个一个算，代码如下，然后超时了。
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int n = nums.size(), cnt = 0;
for (int i=0; i<n-1; i++)
for (int j=i+1; j<n; j++) {
int tmp = nums[i] ^ nums[j];
while (tmp) {
tmp &= (tmp - 1);
cnt++;
}
}
return cnt;
}
};
后来一位一位的算，然后AC了，代码如下：
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int n = nums.size(), cnt = 0;
for (int i=0; i<32; i++) {
int numZeroes = 0, numOnes = 0;
for (int j=0; j<n; j++) {
if (nums[j] % 2 == 0)
numZeroes++;
else
numOnes++;
nums[j] /= 2;
}
cnt += numZeroes * numOnes;
}
return cnt;
}
};
看看大神们简洁的做法，直接移位加与操作：
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int n = nums.size(), cnt = 0;
for (int i=0; i<32; i++) {
int numOnes = 0;
for (int j=0; j<n; j++)
numOnes += (nums[j] >> i) & 1;
cnt += numOnes * (n - numOnes);
}
return cnt;
}
};
