05 August 2008
两个整数之间的汉明距离是对应位不同的位置数。
给定一个整数数组 nums，返回 nums 中所有整数对之间的汉明距离之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
/*
For each bit position 1-32 in a 32-bit integer, we count the number of integers in the array which have that bit set. Then, if there are n integers in the array and k of them have a particular bit set and (n-k) do not, then that bit contributes k*(n-k) hamming distance to the total.
*/
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 total;
}
}