YSMull
<-- Algorithm

Total Hamming Distance

题目连接

题目描述

给一组数,计算所有两两之间汉明距离的和。

分析

  1. 遍历数组,计算 n(n-1)/2 次累加。但是这样做,时间复杂度比较高,最后超时了。
  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;
    }
}