LeetCode 477. 汉明距离总和

Categories:

题目描述
思路分析
1. 解法一：按位计数（推荐）
相似题目

题目描述

✅ 477. 汉明距离总和

思路分析

解法一：按位计数（推荐）

核心思路：

对每一位统计 1 的数量为 ones，0 的数量为 n - ones。

该位对总汉明距离贡献为 ones * (n - ones)。

对 0~30 位累计即可。

复杂度分析：

时间复杂度：O(31n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length;
        int total = 0;

        for (int bit = 0; bit < 31; bit++) {
            int ones = 0;
            for (int num : nums) {
                if (((num >> bit) & 1) == 1) {
                    ones++;
                }
            }
            total += ones * (n - ones);
        }

        return total;
    }
}

func totalHammingDistance(nums []int) int {
	n := len(nums)
	total := 0

	for bit := 0; bit < 31; bit++ {
		ones := 0
		for _, num := range nums {
			if (num>>bit)&1 == 1 {
				ones++
			}
		}
		total += ones * (n - ones)
	}

	return total
}

相似题目

题目	难度	考察点
461. 汉明距离	简单	位运算
191. 位1的个数	简单	位运算
338. 比特位计数	简单	位运算
201. 数字范围按位与	中等	位运算
762. 二进制表示中质数个计算置位	简单	位运算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/54069594