LeetCode 477. Total Hamming Distance（medium难度c++）

题目： 

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.

思路： 
该题目为之前求汉明距离题目的升级版，改为求一个数组中每两个数字的汉明距离之和。最直接的思路当然是用枚举法，一一列举出所有的组合数目，分别求汉明距离之后再求和。思路很直接，但是会超时（貌似O（n^2）复杂度的算法在leetcode上都会超时），需要另辟蹊径

不妨换一种思路，引入最低有效位（ least significant bit，LSB）的概念，指代一个二进制数中的第0位（也就是最低位）。假设vector中一共有K个数字，我们注意到，每个数字的LSB位置为0或者1直接决定最后为总的汉明距离是否有贡献。那我们的思路就变为：

while（所有的数字都不为0）

{

求每个数字的LSB

计算对汉明距离的贡献

每个数字右移1位

}

由于数字给定范围，可以确定移位次数最多不超过32；对于K个数字的LSB，假设有n个数字（设为集合M）最低位为0，则有k-n个数字（设为集合N）最低位为1，当我们任选个数字，有两种情况：

• 这两个数字均来自集合M和集合N，那么对总的汉明距离贡献为0；（因为1^1  0^0 均为0）
• 这两个数字一个来自集合M，一个来自集合N，那么总的汉明距离加一；

显然我们只需要考虑第二种情况，第二种情况的总数为n*(k-n)，此时所有数字的LSB位置对总的汉明距离贡献为n*(k-n)

所有数字右移一位，重复以上步骤，将每次的汉明距离贡献累加求和，知道所有数字均为0，将求和结果返回即可

复杂度分析： 

外层循环32次，内层循环数目为nums中的数字个数，所以整体复杂度O(n)，效率非常高的解法

程序如下：

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int result = 0;  //用来记录汉明距离
        for (int i = 0; i < 32; i++)  //题目中给定数字小于10^9,所以该数字一定不超过32位 
        {
            int zeroCount = 0; //用来表示每次最低有效位上0的数量
            for (int j = 0; j < nums.size(); j++)
            {
                if (nums[j] % 2 == 0)
                    zeroCount++;
                nums[j] = nums[j] >> 1;
                
            }
            result += zeroCount*(nums.size() - zeroCount);
        }
        return result;
    }
};

 

当然，为了让程序更简洁，我们可以换一种写法，思路不变：

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int result = 0;  //用来记录汉明距离
        for (int i = 0; i < 32; i++)
        {
            int oneCount = 0; //用来表示每次最低有效位上0的数量
            for (int j = 0; j < nums.size(); j++)
            {
                if ((nums[j]>>i) & 1 == 1)
                    oneCount++;
            }
            result += oneCount*(nums.size() - oneCount);
        }
        return result;
    }
};

至此该题目已经解答完毕，最后再附上最基础的冒泡排序的解题方法，时间复杂度O（n^2），思路完全没问题，新手经常会想到这样做，但是会报超时，所以正式做题时还是不推荐使用这种方法，程序如下：

class Solution
{
public:
    int totalHammingDistance(vector<int>& nums) {  //枚举法，复杂度O(n^2)估计要超时
        int totalDistance = 0;
        for (int i = 0; i < nums.size() - 1; i++)
            for (int j = i + 1; j < nums.size(); j++)
            {
                int temp = nums[i] ^ nums[j];
                while (temp)
                {
                    if (temp % 2 == 1)
                        totalDistance++;
                    temp = temp >> 1;
                }
            }
        return totalDistance;
    }
};