477. 汉明距离总和

Posted on 2019-10-07 In Leetcode Views: Disqus:

LeetCode刷题系列。

描述

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

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

示例:

输入: 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。

来源：力扣（LeetCode）
链接：477. Total Hamming Distance

解题思路

在461. 汉明距离的基础上，很容易直接套两个遍历，两两计算数组当中各个整数之间的汉明距离，然后累加，具体代码见解法一。

很遗憾，在注意事项里面提到数组的最大长度可能为 $10^4$ ，在极端情况下这样一个 $O(N^2)$ 时间杂度的算法超时了。

既然这样横着两两组合不可行，那么就竖着来。

我们经常会这样分析问题：最简单的情况 -> 一般的、复杂的情况。之前我们是：只有一个两两组合，即上面提到的的做过的461. 汉明距离 -> 遍历所有可能的两两组合。

现在我们换一个角度看：如果int只有1位-> int有32位。

首先，如果int只有1位，即数组nums中的元素只有两种情况，0或者1，此时求汉明距离总和的步骤如下：

首先将数组分成两组，全0位一组，全1位一组
将两组数两两组合，记一个为a，一个为b
如果a、b均来自0那一组，或者均来自1那一组，此时不会有汉明距离产生。但是如果a、b一个来自0那一组，另外一个来自1那一组，这时将会产生汉明距离
假设nums数组元素个数为n，其中0元素个数为k，则1元素的个数为n-k，则上一步能够产生汉明距离的总和就是k*(n-k)
k*(n-k)就是int只有1位的情况下的汉明距离总和

如果将int的位数从1位扩展到32位，那么就是将遍历每一位，然后求出在这一位上的汉明距离和，累加到一起，这样可以将算法复杂度从 $O(N^2)$ 降低到 $O(32\times N)$ ，即为 $O(N)$ 。

可以看下面这个例子：

十进制      二进制
4:         0 1 0 0

14:        1 1 1 0

2:         0 0 1 0

1:         0 0 0 1

先看最后一列，有三个0和一个1，那么它们之间相互的汉明距离就是3，即1和其他三个0分别的距离累加，然后在看第三列，累加汉明距离为4，因为每个1都会跟两个0产生两个汉明距离，同理第二列也是4，第一列是3。各列相互之间两两组合的汉明距离总和就是各列0的个数与1的个数之和，把各列汉明距离总和再累加就是题目所求的数组nums元素两两之间的汉明距离总和。

搞清楚这个规律，问题就迎刃而解了，具体代码见解法二。

代码

解法一

int hammingDistance(int x, int y)
{
    int xor = x^y;
    
    int result = 0;
    
    while(xor)
    {
        result++; 
        xor &= (xor - 1);
    }
    
    return result;
}


int totalHammingDistance(int* nums, int numsSize)
{
    int sum = 0;
    for(int i = 0; i < numsSize; i++)
        for(int j = i+1; j < numsSize; j++)
            sum += hammingDistance(nums[i], nums[j]);
    
    return sum;
}

解法二

int totalHammingDistance(int* nums, int numsSize)
{
    int sum = 0;
    
    for(int i = 0; i < 32; i++)
    {
        int count = 0; 
        
        for(int j = 0; j < numsSize; j++)
        {
            count += (nums[j] >> i) & 1;
        }
        
        sum += count * (numsSize - count);
    }
         
    return sum;
}

描述

解题思路

代码

解法一

解法二

参考