leetcode [477] 汉明距离总和

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

示例:

输入: 4, 14, 2

输出: 6

解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

注意:

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

来自思路：

到达10^4级别，不可以接受，运行超时。

类似的遍历比较，如果转变思维，从逐一数字的横向比较，转变为纵向的逐位比较，往往可以优化。

对于每一个数的某一位来说，若当前位为 1，那么对于当前位来说，所有数字的同位上为 0 的个数即当前数字当前位的汉明距离。

对于本题来说，记录所有数字的每一位的0 1情况，再遍历32位即可。

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        res = 0
        count_1 = [0] * 32
        for val in nums:
            idx = 0
            while val:
                if val & 1:
                    count_1[idx] += 1
                val >>= 1
                idx += 1
        LENGTH = len(nums)
        for val in count_1:
            res += (LENGTH - val) * val
        return res