友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
477. 汉明距离总和
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
给你一个整数数组 nums，请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。
示例 1：
输入：nums = [4,14,2] 输出：6 解释：在二进制表示中，4 表示为 0100 ，14 表示为 1110 ，2表示为 0010 。（这样表示是为了体现后四位之间关系） 所以答案为： HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6
示例 2：
输入：nums = [4,14,4] 输出：4
提示：
-
1 <= nums.length <= 104 -
0 <= nums[i] <= 109 -
给定输入的对应答案符合 32-bit 整数范围
思路分析
对数组遍历，取两个数分别计算汉明距离。利用 Map 缓存结果，避免重复计算。
一个更快的计算方法是：通过求所有数字在一个指定比特位上的 1（c） 和 0（n - c） 数量，再相乘 \(c*(n-c)\)，就这个比特位上的汉明距离，最后把每一位的汉明距离相加，得到汉明距离的总和。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 优化前：通过 35 / 46 个测试用例。
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-09-03 22:03:55
*/
public int totalHammingDistance(int[] nums) {
int result = 0;
for (int i = 0; i < 30; i++) {
int cnt = 0;
for (int num : nums) {
cnt += (num >> i) & 1;
}
result += cnt * (nums.length - cnt);
}
return result;
}