477. Total Hamming Distance

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, 2Output: 6Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (justshowing 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: Elements of the given array are in the range of 0 to 10^9 Length of the array will not exceed 10^4.

思路： 考虑所有数字的同一个bit位，统计在这个bit位上出现的1的次数count，那么这个bit位在总的汉明距离中就贡献了count*(n-count)，n是数组中元素的个数。

class Solution { public int totalHammingDistance(int[] nums) { int total = 0, n = nums.length; for (int j = 0; j < 32; j++) { int bitCount = 0; for (int i = 0; i < n; i++) bitCount += (nums[i] >> j) & 1; total += bitCount*(n - bitCount); } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。