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。 自建示例 -------- 三组数对贡献相同距离: .. code-block:: text 输入:nums = [1, 2, 7] 输出:6 解释:1 与 2、1 与 7、2 与 7 的汉明距离都为 2,三个无序数对总和为 6。 相同整数之间距离为零: .. code-block:: text 输入:nums = [4, 4] 输出:0 解释:两个下标构成一个数对,但对应二进制位完全相同。 按位统计一方为 1、另一方为 0 ------------------------------ 固定某一个二进制位,设数组中有 ``ones`` 个数在该位为 1,``zeros = n - ones`` 个数为 0。这个位对总汉明距离的贡献就是从两类中各选一个的 ``ones * zeros``,因为每个无序下标对只在该位不同一次。 对所有有效位累加即可,不需要枚举 ``O(n^2)`` 个数对。不同下标的重复数值也会被分别放入计数,符合题目的下标计数规则。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int totalHammingDistance(std::vector& nums) { long long answer = 0; int n = static_cast(nums.size()); for (int bit = 0; bit < 31; ++bit) { int ones = 0; for (int value : nums) { if (value & (1 << bit)) ++ones; } answer += static_cast(ones) * (n - ones); } return static_cast(answer); } }; 代码分析 -------- 每个数对在每个二进制位上的差异被独立计算,``ones * zeros`` 恰好枚举该位的两种取值组合,因此不存在重复或遗漏。输入上界小于 ``2^30``,检查 31 位足够;时间复杂度为 ``O(31n)``,额外空间复杂度为 ``O(1)``。