本文共 1246 字，大约阅读时间需要 4 分钟。

477. 汉明距离总和

题目

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。计算一个数组中，任意两个数之间汉明距离的总和。

示例

输入: 4, 14, 2输出: 6解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）所以答案为：HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

题解

方法一：刚开始暴力双循环两两判断结果超时，代码如下：

int sum=0;for(int i=0;i
   
    =0&&len2>=0){            //公共部分进行比较            if(s1.charAt(len1)!=s2.charAt(len2)){                res++;            }            len1--;            len2--;        }        while (len1>=0){            if(s1.charAt(len1)=='1'){                res++;            }            len1--;        }        while (len2>=0){            if(s2.charAt(len2)=='1'){                res++;            }            len2--;        }        sum+=res;    }}return sum;
   

方法二：逐为进行统计

因为数组中的数最大的是10的9次方，小于2的30次方，所以30位二进制位足以表示数组中的数字，我们统一对数组中的某一位进行判断，比如说最低位，我们统计所有数字的最低为中1的个数c，也可以得到长度n-c是0的个数，所以最低为的汉明码距离就是c*(n-c)。然后逐次移位进行判断叠加，最终得到全部的汉明码距离。

• 代码如下

class Solution {    public int totalHammingDistance(int[] nums) {        //采用按位与的方法        int ans=0;        int n=nums.length;        for(int i=0;i<30;++i){            int c=0;//记录有多少个1            for(int num:nums){                c+=(num>>i)&1;            }            ans+=c*(n-c);        }        return ans;    }}

转载地址：http://otgji.baihongyu.com/