477. Total Hamming Distance

题目描述和难度

  • 题目描述：

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

计算一个数组中，任意两个数之间汉明距离的总和。

示例:

输入: 4, 14, 2

输出: 6

解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

注意:

  1. 数组中元素的范围为从 0到 10^9。
  2. 数组的长度不超过 10^4。

思路分析

求解关键：题目要求“ 计算一个数组中，任意两个数之间汉明距离的总和。”这里的关键字是“任意”和“总和”。

  • 一个数要与这个数组中的其他所有数都进行一次汉明距离的计算，然后再把所有的汉明距离求和。
  • 一个整数有 32 位，可以统计计算每 1 位上，所有数组中的这些数上的 1 和 0 的个数，把它们相乘，就是这个数位上对最终结果的“贡献”。
  • 可以举出具体的例子来理解这个算法，其实无非就是把加法变成了乘法。

例如：

1000
1100
0111
0101

这 4 个数，先从最低位开始看起，有 2 个 0 和 2 个 1：1 个 0 与 2 个 1 贡献了 2 个汉明距离，那么 2 个 0 与 2 个 1 就贡献了 $2 \times 2 = 4$ 个汉明距离。

  • 这里有一个比较常见的技巧，使用一个名为 mask 的变量，这个编码只有最高位是 1 ，其余位都是 0，去判断一个数位是否是 1。

参考解答

参考解答1

public class Solution2 {

    public int totalHammingDistance(int[] nums) {
        int len = nums.length;
        int mask = 1;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            // 0 的个数
            int zeros = 0;
            for (int num : nums) {
                if ((num & mask) == 0) {
                    zeros++;
                }
            }
            res += ((len - zeros) * zeros);
            mask <<= 1;
        }
        return res;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0477-total-hamming-distance ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。