LeetCode 477.汉明距离之和 - JavaScript
题目描述：计算一个数组中，任意两个数之间汉明距离的总和。
注意:
- 数组中元素的范围为从 0 到 10^9 。
- 数组的长度不超过 10^4 。
题目分析
如果想了解汉明距离的相关知识，请参考：LeetCode 461.汉明距离。里面介绍了两种做法：
- 使用掩码
- 使用布赖恩·克尼根算法
但本题要求计算数组中任何两数之间的汉明距离，因此若是两两组合，直接计算汉明距离，最后再统计总和，那么时间复杂度是O(k*N^2) ，其中 k 是位数。时间复杂度过高，无法达到要求。
解法：按位统计
按位统计的算法流程是：
- 准备数组 res，
res[i]代表第 i 位为 1 的数字的数目 - 循环遍历 nums，对每一位 i 更新对应的
res[i] - 统计所有位的汉明距离的和，其中第 i 位上的汉明距离之和是：
res[i] * (nums.length - res[i])
注意：根据题目要求，数字的大小不超过 10^9，所以只需要用 30 个二进制表示数字即可。
代码实现如下：
// ac地址：https://leetcode-cn.com/problems/total-hamming-distance/
// 原文地址：https://xxoo521.com/2020-03-04-total-hamming-distance/
/**
* @param {number[]} nums
* @return {number}
*/
var totalHammingDistance = function(nums) {
// 根据题目要求，不超过10^9，所以30位就可以了
const res = new Array(30).fill(0);
for (let num of nums) {
let bit = 0;
let mask = 0x01;
while (bit < 30) {
if (num & mask) {
++res[bit];
}
++bit;
mask = mask << 1;
}
}
const length = nums.length;
return res.reduce((pre, cur) => pre + cur * (length - cur), 0);
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-03-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
