LeetCode 477 Total Hamming Distance

LeetCode

题目描述

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.

Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

题目分析

此题和第 461 题很像，初看是 461 题目的延伸。按照那道题的思路来做就是：

1. 对数组中所有的数进行两两组合
2. 对于每两个数的组合，求一次 Hamming Distance

但是这样做会超时，是因为两两组合的时间复杂度是 O(n^2)，而求一次组合也需要最多 32 次循环。

那么应该怎么做这道题目呢？题目中的 Explanation 其实是一种误导，我们真的有必要两两组合分别求 Hamming Distance 吗？其实是没有必要的，一次循环能否取得所有的 Hamming Distance？

通过分析得出，Hamming Distance 其实就是每一位的异同。那么这道题目就可以转化为：求x个数每两个数的组合中，每一位的异同数量。想到这里，就会发现其实x个数中每个数的数值并不重要，重要的是每一位有多少个0和多少个1。

假设有x个数中，第一位有m个0，n个1，则该位的Hamming Distance 是：m * n。

代码

public int totalHammingDistance(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }
    int[] m = new int[31];// 存储对应位数，有多少个0
    for(int num : nums) {
        for(int i = 0; i < 31; i++) {
            if ((num & (1 << i)) == 0) {
                m[i]++;
            }
        }
    }
    int result = 0;
    for(int i = 0; i < 31; i++) {
        result += m[i] * (nums.length - m[i]);
    }
    return result;
}