2017/03/22
题目描述
给一组数，计算所有两两之间汉明距离的和。
分析
- 遍历数组，计算 n(n-1)/2 次累加。但是这样做，时间复杂度比较高，最后超时了。
- 对于数组中所有数字的同一位来说，如果有 p 个数在这一位是 1，q 个数在这一位是 0,那么这一位对总汉明距离的贡献量为 p*q，因为满足这一位的汉明距离为1的组合有 p*q 对。思路来源
代码
int totalHammingDistance(int* nums, int numsSize) {
int sum = 0;
while (true) {
int zeroNum = 0;
int p0 = 0, p1 = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 0) zeroNum++;
nums[i] % 2 == 0 ? p0++ : p1++;
nums[i] >>= 1;
}
sum += p0*p1;
if (zeroNum == numsSize) return sum;
}
}