原文链接: https://leetcode-cn.com/problems/total-hamming-distance

英文原文

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

 

Example 1:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

Input: nums = [4,14,4]
Output: 4

 

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 109
• The answer for the given input will fit in a 32-bit integer.

中文题目

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

给你一个整数数组 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 整数范围

通过代码

高赞题解

按位统计

我们知道，汉明距离为两数二进制表示中不同位的个数，同时每位的统计是相互独立的。

即最终的答案为 $\sum_{x = 0}^{31} calc(x)$，其中 $calc$ 函数为求得所有数二进制表示中的某一位 $x$ 所产生的不同位的个数。

我们考虑某个 $cacl(x)$ 如何求得：

事实上，对于某个 nums[i] 我们只关心在 nums 中有多少数的第 $x$ 位的与其不同，而不关心具体是哪些数与其不同，同时二进制表示中非 $0$ 即 $1$。

这指导我们可以建立两个集合 $s0$ 和 $s1$，分别统计出 nums 中所有数的第 $x$ 位中 $0$ 的个数和 $1$ 的个数，集合中的每次计数代表了 nums 中的某一元素，根据所在集合的不同代表了其第 $x$ 位的值。那么要找到在 nums 中有多少数与某一个数的第 $x$ 位不同，只需要读取另外一个集合的元素个数即可，变成了 $O(1)$ 操作。那么要求得「第 $x$ 位所有不同数」的对数的个数，只需要应用乘法原理，将两者元素个数相乘即可。

前面说到每位的统计是相对独立的，因此只要对「每一位」都应用上述操作，并把「每一位」的结果累加即是最终答案。

代码：

[]
class Solution {
    public int totalHammingDistance(int[] nums) {
        int ans = 0;
        for (int x = 31; x >= 0; x--) {
            int s0 = 0, s1 = 0;
            for (int u : nums) {
                if (((u >> x) & 1) == 1) {
                    s1++;
                } else {
                    s0++;
                }  
            }
            ans += s0 * s1;
        }
        return ans;
    }
}

• 时间复杂度：$O(C * n)$，$C$ 固定为 $32$
• 空间复杂度：$O(1)$

统计信息

通过次数	提交次数	AC比率
39662	65706	60.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
汉明距离	简单