frendguo's blog

【LeetCode】477. Total Hamming Distance

原文地址:https://leetcode.com/problems/total-hamming-distance/#/description

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 to 10^9
  2. Length of the array will not exceed 10^4.

初的一看,这不是和 【LeetCode】461. Hamming Distance 类似的嘛,就是依次进行计算汉明距离,最后都加起来~于是就有下面的代码:

public static int TotalHammingDistance(int[] nums)
{
	if (nums.Length <= 0)
	{
		return 0;
	}
	int res = 0;
	for (int i = 0; i < nums.Length; i++)
	{
		for (int j = i + 1; j < nums.Length; j++)
		{
			res += HammingDistance(nums[i], nums[j]);
		}
	}

	return res;
}

static int HammingDistance(int x, int y)
{
	int tmp = x ^ y;
	int res = 0;
	while (tmp != 0)
	{
		tmp &= (tmp - 1);
		++res;
	}
	return res;
}

然后已提交,果然超时了~

然后发现一个大神的想法,然后实现出来了,简直完美~

public static int TotalHammingDistance(int[] nums)
{
	if (nums.Length <= 0)
	{
		return 0;
	}
	
	int n = nums.Length;
	int bitCount = 0;
	int res = 0;
	for (int i = 0; i < 32; i++)
	{
		bitCount = 0;
		for (int j = 0; j < n; j++)
		{
			bitCount += (nums[j] >> i) & 1;
		}
		res += bitCount * (n - bitCount);
	}
	return res;
}

将数组中的每个数的二进制拆开来看,以列为单位,其中 bitCount 为当前列中 ‘1’ 的个数,那么(n - bitCount) 就是当前列中‘ 0’ 的个数了。而题目的要求则是将每两个数的汉明码距离加起来,也就是每列中 ‘1’ 和 ‘0’ 的组合个数之和。而每列中组合个数则是 bitCount * (n - bitCount) .因此很快的就将总的汉明码距离算出来了~

Happy Coding!o(* ̄▽ ̄*)o

Add comment

Loading