[Leetcode 477] Total Hamming Distance

作者 Shilei Tian 日期 2016-12-28
[Leetcode 477] Total Hamming Distance

题目要求

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.

解题思路

拿到题目,很容易就能想到比较朴素的做法,就是遍历每一对儿数字,求出它们之间的 Hamming distance 然后再加起来,代码如下:

class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int cnt = 0;
for (int i = 0; i < nums.size(); ++i) {
for (int j = i + 1; j < nums.size(); ++j) {
cnt += distance(nums[i], nums[j]);
}
}
return cnt;
}
private:
int distance(int a, int b) {
int cnt = 0;
int d = a ^ b;
while (d) {
cnt += (d & 0x1);
d >>= 1;
}
return cnt;
}
};

这段代码的时间复杂度是 $O(n^2)​$,跑起来会超时。在查看 Top Solutions 以后,学到了一个新的做法。

根据 hamming distance 的定义,其实就是求两个数字每一个 bit 的差。题给的数字都是 int 类型,那么就可以想做每次检查这 32 位中的一位,看一下所有的数字在这一位上能产生多少的 hamming distance,然后将 32 位数字的 hamming distance 加起来即可。

现在的问题就变成,我们有若干个 bit 位,求这些 bit 位两两之间差的绝对值的和。两个 bit 位之间的差能对和作出贡献的,就只有当两个 bit 位不一样的时候。这样,我们可以先将这些 bit 位分成两部分,一部分是 1 的集合表示为 Q,一部分是 0 的集合,表示为 P。只有这两个 bit 位一个来自 P,一个来自 Q,两者的差才可以为 1。那么这种情况有多少种呢?答案就很显然了,这就跟从两个集合任意抽取两个元素一共有多少种可能是一样的:$\vert P \vert\times\vert Q\vert$。

这样,我们每次从左到右(或者从右到左)检查每一位的 hamming distance,然后将它们加起来即可,代码如下:

class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int cnt = 0, p = nums.size();
for (int i = 0; i < 32; ++i) {
int q = 0;
for (auto num : nums) {
if (num & 0x1 == 1) {
++q;
}
}
cnt += q * (p - q);
shift(nums);
}
return cnt;
}
private:
void shift(vector<int>& nums) {
for (auto& num : nums) {
num >>= 1;
}
}
};