DeepSeek LeetCode 477. 汉明距离总和 Java实现

思路按位统计两个数在某一位上不同这一位就对汉明距离贡献 1。对于第 i 位· 统计 nums 中该位为 1 的个数 ones· 该位为 0 的个数为 n - ones· 任意一个「1」和一个「0」的组合都会在这一位上产生 1 个距离所以这一位对总和的贡献是 ones * (n - ones)把所有位题目数据 nums[i] 10^9 2^30遍历 0~30 位即可的贡献累加。Java 实现classSolution{publicinttotalHammingDistance(int[]nums){intnnums.length;longans0;for(inti0;i31;i){intones0;for(intx:nums){ones(xi)1;}ans(long)ones*(n-ones);}return(int)ans;}}复杂度分析· 时间复杂度O(31 * n)即 O(n)n 为数组长度。· 空间复杂度O(1)。细节说明为什么是 31 位 nums[i] 10^9约 2^30取 31 位0~30足够覆盖。为什么中间用 long ones * (n - ones) 最大约为 n^2/4当 n 10^4 时约 2.5 * 10^7再乘位数仍可能接近 int 上限使用 long 累加避免溢出。与暴力 O(n^2) 两两比较相比按位统计是本题的标准最优解。示例输入: nums [4, 14, 2] 输出: 6 二进制: 4 0100 14 1110 2 0010逐位看· 第 1 位1 的个数 20 的个数 1 → 2×1 2· 第 2 位1 的个数 20 的个数 1 → 2· 第 3 位1 的个数 10 的个数 2 → 2· 其余位全为 0 → 0总和 2 2 2 6 ✓