本文主要是介绍leetcode 477. 汉明距离总和——超出时间限制，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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<nums.length;++i){for(int j=i+1;j<nums.length;++j){int x=nums[i];int y=nums[j];String s1=Integer.toBinaryString(x);String s2=Integer.toBinaryString(y);int len1=s1.length()-1;int len2=s2.length()-1;int res=0; //用来记录海明次数while (len1>=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;//记录有多少个1for(int num:nums){c+=(num>>i)&1;}ans+=c*(n-c);}return ans;}
}
这篇关于leetcode 477. 汉明距离总和——超出时间限制的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
