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