LeetCode 477. 汉明距离总和
题目描述
题意分析
汉明距离是两个数的二进制表示中不同位的数量。要统计所有下标对
i<j的距离总和，即每对元素只计算一次；某一位不同贡献1，与这一位的数值权重无关。逐对异或需要枚举平方数量的数对。由于每一位的贡献相互独立，可以交换统计顺序，先算每一位有多少数对不同，再把各位贡献相加。
解法：按位计数
核心思路
[!blue]
固定第
bit位，把数组元素按这一位是1还是0分为两组。设第一组有ones个元素，第二组就有n-ones个。同组内两数在这一位相同，贡献为零；异组各取一个数，恰好贡献一次差异，所以本位贡献是ones*(n-ones)。每个异组无序数对，都唯一对应它的那个
1元素与那个0元素，因此这个乘积没有重复计数，不需要再除以2。即使数组中有相同数值，它们仍按各自下标参与分组，计数方式不变。用
(num >> bit) & 1读取当前位，每一位重新统计ones后累加贡献。遍历完所有可能出现的位后，每个数对的每一处差异都恰好被加了一次，得到的就是全部汉明距离之和。
解题步骤
- 每一位开始时清空一的计数。
- 扫描数组，用移位和与一取得当前位。
- 累加
ones*(n-ones)。题目元素为非负数且不超过
10^9，第0到第29位足够；现有代码多扫描第30位，该位全零，贡献仍为零。只有一个元素或全部元素相等时，每一位都只有一个非空组，答案自然为零。
代码实现
class Solution {
public int totalHammingDistance(int[] nums) {
int n = nums.length;
int total = 0;
for (int bit = 0; bit < 31; bit++) {
// 每一位独立统计，不能继承上一位的计数
int ones = 0;
for (int num : nums) {
if (((num >> bit) & 1) == 1) {
ones++;
}
}
// 两组各取一个已是无序数对数量，不需要除二
total += ones * (n - ones);
}
return total;
}
}
func totalHammingDistance(nums []int) int {
n := len(nums)
total := 0
for bit := 0; bit < 31; bit++ {
// 每一位独立统计，不能继承上一位的计数
ones := 0
for _, num := range nums {
if (num>>bit)&1 == 1 {
ones++
}
}
// 两组各取一个已是无序数对数量，不需要除二
total += ones * (n - ones)
}
return total
}
复杂度分析
- 时间复杂度：$O(n)$，现有代码对每个元素固定检查
31位。- 空间复杂度：$O(1)$，每位共用同一个计数器。
关键点总结
[!green]
- 按位统计把所有数对的比较压缩成两个组的数量相乘。
- 汉明距离统计的是不同位数，每个不同位只贡献
1。
易错点总结
[!yellow]
- 把乘积除二，会少算一半。
- 使用掩码提取某位后，要判断它是否为零，不能把掩码的位权直接加入
ones。- 不同位之间不清零，会混合本来独立的统计。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 461. 汉明距离 | 简单 | 原题只计算两个数，本题按位累计cnt0×cnt1，避免枚举所有数对。 |
| 191. 位1的个数 | 简单 | 同样逐位统计1，但本题统计同一位在全部数中的出现次数而非一个数的总置位数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！