477. Total Hamming Distance总的二进制距离

［抄题］：

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just

showing the four bits relevant in this case). So the answer will be:

HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

以为要在数字之间两两选择

［一句话思路］：

从32个格子的角度思考，个格子中做全排列

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

num_of_ones不是一次位运算出来的，而是逐步和第j位取&后求和累加出来的

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

从32个格子的角度思考，32个格子中做全排列

［复杂度］：Time complexity: O(n) Space complexity: O(1)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［算法思想：递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

class Solution {

    public int totalHammingDistance(int[] nums) {

        //cc

        if (nums == null || nums.length == 0) return 0; 

        //ini:

        int res = 0;

        //for loop in 32 bit

        for (int i = 0; i < 32; i++) {

            int nums_of_ones = 0;

            for (int j = 0; j < nums.length; j++)

                nums_of_ones += (nums[j] >> i) & 1;

            res += nums_of_ones * (nums.length - nums_of_ones);

        }

        return res;

    }

}

[代码风格] ：

巴特西

477. Total Hamming Distance总的二进制距离

最新文章

热门文章