题目描述：

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.

题目大意：

两个整数的汉明距离是指其二进制不相等的位的个数。

计算给定的整数数组两两之间的汉明距离之和。

注意：

1. 元素大小在[0, 10^9]之间。
2. 数组长度不超过10^4。

解题思路：

按位统计各整数的二进制0与1的个数之和，分别记为zero[i], 和one[i]

ans = ∑(zero[i] * one[i]),  i∈[0, 31]

Python代码：

class Solution(object):
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        for x in range(32):
            mask = 1 << x
            zero = one = 0
            for num in nums:
                if num & mask:
                    one += 1
                else:
                    zero += 1
            ans += zero * one
        return ans

 

本文链接：http://bookshadow.com/weblog/2016/12/18/leetcode-total-hamming-distance/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码