leetcode-total-hamming-distance

题目大意

  https://leetcode.com/contest/leetcode-weekly-contest-13/problems/total-hamming-distance/

  求n个整数的任意两个数的汉明距离之和。

题目分析

  首先求两个数的汉明距离之和,可以进行逐位比较,也可以求两个数的异或,然后统计1的个数。如果求n个数的两两汉明距离之和需要一些技巧,应该逐位比较,在每一位上如何计算两两距离之和?由乘法原理,其实只要计算0的个数再乘以1的个数即可,最后逐位之和累加。  

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
private int hammingDistance(int x, int y) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int cx = x & (1 << i);
int cy = y & (1 << i);
if (cx != cy) {
ans++;
}
}
return ans;
}
public int totalHammingDistance(int[] nums) {
int len = nums.length;
int ans = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
for (int j = 0; j < len; j++) {
if (((1 << i) & nums[j]) > 0) {
count++;
}
}
ans += (len - count) * count;
}
return ans;
}
}

  复杂度:O(n * 32)