Total Hamming Distance,LeetCode,477

LeetCode 477题 “Total Hamming Distance” 是一个中等难度的位操作问题。题目要求计算一个数组中所有数对之间的汉明距离的总和。汉明距离是指两个整数对应二进制位不同的位置的数目。

题目描述

给定一个非空整数数组 nums，返回数组中所有数对之间的汉明距离的总和。

示例

输入: nums = [4, 14, 2] 输出: 6 解释: 在二进制表示中，4表示为 0100，14表示为 1110，2表示为 0010。 所以它们之间的汉明距离分别为： HammingDistance(4, 14) = 2 HammingDistance(4, 2) = 2 HammingDistance(14, 2) = 2 所以总汉明距离为 6。

解法思路

直接计算每两个数之间的汉明距离会导致时间复杂度为 O(n^2)，我们可以通过位操作优化到 O(n)。

核心思想：

1. 对于每一个二进制位，统计数组中在该位上为 1 的数的个数。
2. 对于每一位，汉明距离的贡献为该位上为 1 的数的个数乘以该位上为 0 的数的个数。

具体步骤

1. 初始化 total_distance 为 0。
2. 遍历每一位（从 0 到 31，假设数组中的数不超过 2^31 – 1）。
3. 对于每一位，统计数组中在该位上为 1 的数的个数 count_1。
4. 该位的汉明距离贡献为 count_1 * (n - count_1)，其中 n 是数组的长度。
5. 将该位的贡献加到 total_distance 中。
6. 返回 total_distance。

代码实现

class Solution: def totalHammingDistance(self, nums): total_distance = 0 n = len(nums)

    for i in range(32):  # 遍历每一位
        count_1 = 0
        for num in nums:
            count_1 += (num >> i) & 1  # 统计在第 i 位上为 1 的数的个数
        count_0 = n - count_1
        total_distance += count_1 * count_0  # 计算该位的汉明距离贡献

    return total_distance

解释

• (num >> i) & 1：将 num 右移 i 位后与 1 进行按位与操作，得到第 i 位的值。
• count_1 * count_0：在第 i 位上，为 1 的数和为 0 的数之间的汉明距离贡献。

复杂度分析

• 时间复杂度：O(n * 32) = O(n)，因为我们需要遍历每一位，共 32 位，每次遍历数组。
• 空间复杂度：O(1)，只使用了常数额外空间。

通过这种方法，我们能够高效地计算出数组中所有数对之间的汉明距离的总和。希望这个解释对你理解这道题有所帮助！如果有更多问题，欢迎继续提问。