0477. Total Hamming Distance

题目信息

题号:

0477

难度:

Medium

主题:

非负整数数组、无序数对、二进制不同位、距离总和

原题:

LeetCode 0477

重点:

对所有 i < j 的数对分别计算、相同数值的不同下标仍是一个数对、每对只计一次

题目重述

给定非负整数数组 nums,对所有满足 0 <= i < j < nums.length 的无序下标对,计算 nums[i] 与 nums[j] 的汉明距离,并返回这些距离的总和。

两个整数的汉明距离是二进制表示中对应位不同的数量。nums.length 位于 [1, 10^4],每个元素位于 [0, 10^9]。重复数值位于不同下标时仍会形成数对,只是它们之间的距离可能为 0。

自建示例

三组数对贡献相同距离:

输入:nums = [1, 2, 7]
输出:6
解释:1 与 2、1 与 7、2 与 7 的汉明距离都为 2,三个无序数对总和为 6。

相同整数之间距离为零:

输入:nums = [4, 4]
输出:0
解释:两个下标构成一个数对,但对应二进制位完全相同。

按位统计一方为 1、另一方为 0

固定某一个二进制位,设数组中有 ones 个数在该位为 1,zeros = n - ones 个数为 0。这个位对总汉明距离的贡献就是从两类中各选一个的 ones * zeros,因为每个无序下标对只在该位不同一次。

对所有有效位累加即可,不需要枚举 O(n^2) 个数对。不同下标的重复数值也会被分别放入计数,符合题目的下标计数规则。

C++ 实现

class Solution {
public:
    int totalHammingDistance(std::vector<int>& nums) {
        long long answer = 0;
        int n = static_cast<int>(nums.size());
        for (int bit = 0; bit < 31; ++bit) {
            int ones = 0;
            for (int value : nums) {
                if (value & (1 << bit)) ++ones;
            }
            answer += static_cast<long long>(ones) * (n - ones);
        }
        return static_cast<int>(answer);
    }
};

代码分析

每个数对在每个二进制位上的差异被独立计算,ones * zeros 恰好枚举该位的两种取值组合,因此不存在重复或遗漏。输入上界小于 2^30,检查 31 位足够;时间复杂度为 O(31n),额外空间复杂度为 O(1)。