Medium

题目描述

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

给你一个整数数组 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 <= 10^4
  • 0 <= nums[i] <= 10^9
  • 给定输入的对应答案符合 32 位整数范围

解题思路

这道题如果暴力求解，需要计算所有数对的汉明距离，时间复杂度为 O(n²)，对于 n=10⁴ 的数据规模会超时。

关键观察是：我们可以按位统计。对于二进制的每一位，统计有多少个数字在这一位上是 1，有多少个是 0。如果有 count1 个 1 和 count0 个 0，那么这一位对总汉明距离的贡献就是 count1 × count0，因为每个 1 都会与每个 0 产生 1 的汉明距离。

具体思路：

  1. 遍历 32 个二进制位（因为题目限制数字不超过 10⁹，在 32 位整数范围内）
  2. 对于每一位，统计数组中有多少个数字在这一位上是 1
  3. 计算这一位的贡献：count1 × (n - count1)
  4. 累加所有位的贡献

这种方法的时间复杂度是 O(32n) = O(n)，空间复杂度是 O(1)。

代码实现

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int n = nums.size();
        int result = 0;
        
        for (int i = 0; i < 32; i++) {
            int count1 = 0;
            for (int num : nums) {
                if ((num >> i) & 1) {
                    count1++;
                }
            }
            result += count1 * (n - count1);
        }
        
        return result;
    }
};

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        n = len(nums)
        result = 0
        
        for i in range(32):
            count1 = 0
            for num in nums:
                if (num >> i) & 1:
                    count1 += 1
            result += count1 * (n - count1)
        
        return result

public class Solution {
    public int TotalHammingDistance(int[] nums) {
        int n = nums.Length;
        int result = 0;
        
        for (int i = 0; i < 32; i++) {
            int count1 = 0;
            foreach (int num in nums) {
                if (((num >> i) & 1) == 1) {
                    count1++;
                }
            }
            result += count1 * (n - count1);
        }
        
        return result;
    }
}

var totalHammingDistance = function(nums) {
    const n = nums.length;
    let result = 0;
    
    for (let i = 0; i < 32; i++) {
        let count1 = 0;
        for (let num of nums) {
            if ((num >> i) & 1) {
                count1++;
            }
        }
        result += count1 * (n - count1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(32n) = O(n)
空间复杂度O(1)

相关题目