leetcode-477-汉明距离总和

汉明距离综合

题面

leetcode题目

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

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

example

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

题解

总体思路

令\(f(x,y)=HammingDistance(x,y)\)表示为\(x\)与\(y\)的汉明距离，考虑对于数组\(a = [a_0,a_1,a_2\cdots a_{n-1}]\)的汉明距离和等于\[f(a_1,a_0) + f(a_2,a_1) + \cdots + f(a_i,a_{i-1}) + f(a_i,a_{i-2}) + \cdots + f(a_{n-1}, a_0) \tag{1}\] 这是显然的，上式子\(\tag{1}\)我们可以这样理解。考虑一个数组中的两两配对，可以按这样的顺序考虑: 对于第\(i\)个元素，与他的前\(i-1\)个元素都进行一次配对，那么到最后所有的元素都能被两两配对。
既然我们已经能表达出这个关系，那么我们再仔细的考虑一下\(f(x,y)\)。\(f(x,y)\)实际上表示\(x\)与\(y\)中二进制位不同的数量，那么对于\(x\)我们可以逐个二进制位进行考虑:

• 如果该二进制位是0，那么如果\(y\)的对应二进制位是1，则不同的数量需要加一。
• 如果该二进制位是1，那么如果\(y\)的对应二进制位是0，则不同的数量需要加一。

到这里，我们再看式\((1)\)，对于通项: \[ f(a_i,a_{i-1}) + f(a_i,a_{i-2}) + \cdots + f(a_i,a_{1}) + f(a_i,a_{0}) \tag{2} \] 我们可以这样考虑，这里计算的是第\(i\)个元素对于前\(i-1\)个元素的汉明距离和，即对应二进制位不同的数量的总和，我们也是逐个二进制位进行考虑:

• 如果\(a[i]\)的当前二进制位为1，那么如果\(a[i-1]\)的二进制位也为1，则总和需要加一。如果\(a[i-2]\)的二进制位也为1，则总和也需要加一，依次考虑\(i-1\)个元素后我们假设\(cnt1\)表示\(i-1\)个元素的对应二进制位为1的数量，则总数需要加\(cnt1\)。
• 如果\(a[i]\)的当前二进制位为0，那么如果\(a[i-1]\)的二进制位也为0，则总和需要加一。如果\(a[i-2]\)的二进制位也为0，则总和也需要加一，依次考虑\(i-1\)个元素后我们假设\(cnt0\)表示\(i-1\)个元素的对应二进制位为0的数量，则总数需要加\(cnt0\)。

这样来看，我们如果逐个元素逐个二进制位的进行考虑，则只需要统计出\(i-1\)个元素的对应二进制1与二进制0的数量即可，这里显然是个前缀和。

代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;

#define _NDEBUG
class Solution
{

    const int MAX = 32;

public:
    int totalHammingDistance(vector<int> &nums)
    {
        int len = nums.size();
        int pre[len + 1][MAX];
        memset(pre, 0, sizeof(pre));
        int ret = 0;
        for (int i = 1; i <= len; i++)
        {
            int num = nums[i - 1];
            for (int j = 0; j < MAX; j++)
            {
                pre[i][j] = pre[i - 1][j];
                int k = (num % 2 == 1);
                int cnt1 = pre[i - 1][j];
                int cnt0 = (i - 1) - pre[i - 1][j];
                if (k == 1)
                {
                    ret = ret + cnt0;
                    pre[i][j]++;
                }
                else
                {
                    ret = ret + cnt1;
                }
#ifdef _DEBUG
                cout << "i: " << i << " j: " << j << " ret: " << ret << endl;
#endif
                num = num / 2;
            }
        }
        return ret;
    }
};

// for test
int main()
{
    Solution s;
    vector<int> t1{4, 14, 2};
    vector<int> t2{1337, 7331};
    //    cout << s.totalHammingDistance(t1) << endl;
    cout << s.totalHammingDistance(t2) << endl;
    return 0;
}