统计海明距离

算法

题意
分析
代码

题意

给定若干个数，计算其中所有数对的海明（Hamming）距离之和。

分析

如果直接计算的话，O(N^2)的代价是不可忍受的。然后就很自然地想到，我们把这个问题横向转化一下：既然海明距离计算的只是每个对应二进制位的差异，那么，我们可以直接对所有数的这一位进行统计，得到0和1的个数，然后计算这一位对整体距离的贡献：count(0) * count(1)

代码

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int zeroBits[31];
        memset(zeroBits, 0, sizeof(zeroBits));
        for (int num: nums) {
            for (int i = 0; i < 31; i++) {
                if ((num & (1 << i)) == 0)
                    zeroBits[i]++;
            }
        }
        int ans = 0, n = nums.size();
        for (int i = 0; i < 31; i++)
            ans += zeroBits[i] * (n - zeroBits[i]);

        return ans;
    }
};

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 yxhlfx@163.com