1. 汉明距离总和
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中,任意两个数之间汉明距离的总和。
问题分析:
看到这个题,我一眼就想到用for循环,但奈何for循环的时间复杂度太高,因此我放弃了~
只要你想学习,生命总会有出路的,不巧,光明就在前方——举个梨子:
2 0010
7 0111
3 0011
最高位:三个0,距离为0
次高位:一个1,两个0,距离12
第2位:三个1,距离0
第1位:两个1,一个0,距离21
总和 = 2 + 2 = 4
所以可以看出,我们需要定义一个数组用来存储每一位的1的个数,接下来用1的个数乘以该位0的个数,得到该位的汉明距离,循环此操作求得汉明距离总和
public int totalHammingDistance(int[] nums) {
if(nums.length<=1){
return 0;
}
int len=nums.length;
int[] sums=new int[32];
int x=0;
/*for(int i=0;i<len;i++){//统计每个二进制位上的1出现个数
for(int j=0;j<32;j++){
sums[j]+=nums[i]&1;
nums[i]=nums[i]>>1;
if(nums[i]==0){
break;
}
}
}
/
for(int i = 0;i<32;i++){
for(int j = 0;j<len;j++){
sums[i]+=nums[j]&1;
nums[j]>>=1;
}
}
int sum=0;
for(int i=0;i<32;i++){//通过对每个二进制位上的1的个数和0的个数相乘,求和
sum+=sums[i](len-sums[i]);
}
return sum;
}
- 求两个数的汉明距离
class Solution {
public int hammingDistance(int x, int y) {
int z = x^y;
int res = 0;
while(z!=0){
/*除余法
if(z%2 == 1){
res++;
}
z = z/2;
*/
/*移位法
res+=z&1;
z>>=1;
*/
/*经典法
z = z &(z – 1);
res++;
*/
}
return res;
}
}