Leetcode 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.

Note:

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

分析：
在leetcode 461中有如何计算海明距离的方法，这里数据长度不超过10^4，讲道理n^2可行，但是还涉及到数据本身长度（虽然长度很短，不超过32），所以还是会tle
所以仔细想想，发现是可以用O(n)的方法来做的

思路：
分别观察每一位，比如所有数的最后一位，假设有m个1，n个0， 那么这一位产生的海明距离之和应该为 m * n（易证）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for i in range(32):
        	# 从最后一位开始
            cnt, mask = 0, 1 << i
            for num in nums:
                # count the number of '1'
                cnt += num & mask != 0
            # cnt '1' and (n-cnt) '0', the distance is the product!
            res += cnt * (len(nums)-cnt)
        return res


# O(n) time, O(1) space
47 / 47 test cases passed.
difficulty: medium
Runtime: 337 ms