477.汉明距离总和

https://leetcode-cn.com/problems/total-hamming-distance/

难度：中等

题目：

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

计算一个数组中，任意两个数之间汉明距离的总和。

注意:

• 数组中元素的范围为从 0到 10^9。
• 数组的长度不超过 10^4。

示例：

输入: 4, 14, 2

输出: 6

解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2)
 = 2 + 2 + 2 = 6.

分析

如果看过我昨天的解题： 461.汉明距离

那么相信今天的题目，只需要简单思考下，就能解决。 昨天是计算两个数的汉明距离，今天无非多几个。
来一个打一个，来两个打一双，来多少都不够塞牙缝的。

2   (0 0 1 0)
4   (0 1 0 0)
14  (1 1 1 0)
     ↑ ↑ ↑ 

查看上图，末尾尾数都是0，不存在汉明距离，其他三位都分别存在0和1，那么这个多位该如何算？
让我们把相同的数放在一起 先这样[1] *[0,0]，然后在看看一共有几种排列？
1的个数 * 0的个数 = 1的个数 * 总数 - 1的个数 = 2 3 * 2 = 6 用例通过。

好了，算法知道了，下来我们来构造矩阵，由于数组元素范围在0 ~ 10 ** 9,10 ** 9 < 2 ** 30.
所以我们构造一个最大1000行的列表，然后计算每一列汉明距离n * (length - n)。
矩阵转置怎么快？zip(*matrix)，转换为31 * 1000的矩阵在进行计算。

解题1 二维矩阵：

class Solution:
    def totalHammingDistance(self, nums):
        ret, ln = 0, len(nums)
        matrix = [bin(num)[2:].zfill(31) for num in nums]
        for row in zip(*matrix):
            n = row.count('1')
            ret += n * (ln - n)
        return ret

上面的方法我们最大可能会构造一个31 * 1000的矩阵，那么有没有拿空间换时间的方法呢？
答案是有的，我们维护一个长度为31的全零数组，然后将二进制的字符串进行倒序后，
判断每一位的结果追加至计数列表。最终循环计算列表的总和即可。

解题2 列表计数器：

class Solution:
    def totalHammingDistance(self, nums):
        count_list = [0] * 31
        ret, ln = 0, len(nums)
        for num in nums:
            for index, s in enumerate(bin(num)[2:][::-1]):
                if s == '1':
                    count_list[index] += 1
        for count in count_list:
            ret += count * (ln - count)
        return ret

欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown