leetcode_477

发表于   |   分类于

Total Hamming Distance

题目戳这

题意

给定一个数组，求数组中两两二进制表示中不同位个数的总和。

解法

数组规模有10^4，所以不能用两层循环。数字的范围小于10^9，所以我们统计32位二进制表示中，每个数组中的元素在某一位是0还是1。如果是1的个数有m个，那么是0的个数就为arr.length-m，则在这一位二进制表示不同位的总和就是 m*(arr.length-m)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        nlen = len(nums)
        
        for i in range(32):
            bt = 0
            for x in nums:
                bt += (x>>i&1)
            ans += (bt)*(nlen-bt)
        
        return ans