echo

任生命穿梭 时间的角落

0%

汉明距离总和

Posted on In Valine:

477. 汉明距离总和

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

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

示例:

1
2
3
4
5
6
7
输入: 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。

方法一：逐位统计

在计算汉明距离时，我们考虑的是同一比特位上的值是否不同，而不同比特位之间是互不影响的。

对于数组 nums 中的某个元素 val，若其二进制的第 i 位为 1，我们只需统计 nums 中有多少元素的第 i 位为 0 ，这样就就得到了 val 与其他元素在第 i 位上的汉明距离之和。

若长度为 n 的数组 nums 的所有元素二进制的第 i 位共有 c 个 1， n - c 个 0，这些元素在二进制第 i 位上的汉明距离位c * (n - c)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length;
        int ret = 0;

        for(int i = 0; i < 30; i++){
            int c = 0;
            for(int num : nums){
                c += (num >> i) & 1;
            }
            ret += c * (n - c);
        }
        return ret;
    }
}
  • 时间复杂度O(n * L)，n 为数组长度，L = 30
  • 空间复杂度O(1)