项目建设管理 公司 网站,wordpress友情首页,怎么做一个论坛网站,针对网站开发者的问答网站两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
给你一个整数数组 nums#xff0c;请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。 示例 1#xff1a;
输入#xff1a;nums [4,14,2]
输出#xff1a;6
解释#xff1a;在二进制表示中请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。 示例 1
输入nums [4,14,2]
输出6
解释在二进制表示中4 表示为 0100 14 表示为 1110 2表示为 0010 。这样表示是为了体现后四位之间关系
所以答案为
HammingDistance(4, 14) HammingDistance(4, 2) HammingDistance(14, 2) 2 2 2 6示例 2
输入nums [4,14,4]
输出4提示
1 nums.length 1040 nums[i] 109给定输入的对应答案符合 32-bit 整数范围
超时版本使用异或来查找1的个数由于最后统计时O(N^2)所以超时
class Solution:def totalHammingDistance(self, nums: List[int]) - int:nlen(nums)res0def HammingDistance(a,b):ans0flaga^bwhile flag:if flag11:ans1flagflag1return ansif n2:return HammingDistance(nums[0],nums[1])for i in range(n-1):for j in range(i1,n):resHammingDistance(nums[i],nums[j])return res
巧解版本
class Solution:def totalHammingDistance(self, nums: List[int]) - int:n len(nums)total_distance 0for bit in range(32):count_ones sum(((num bit) 1) for num in nums)count_zeros n - count_onestotal_distance count_ones * count_zerosreturn total_distance
在汉明距离的计算中对于一个特定的比特位假设有count_ones个数的该比特位是1有count_zeros个数的该比特位是0。那么在这个比特位上的汉明距离之和就是count_ones乘以count_zeros。
这是因为在这个比特位上count_ones个数的1与count_zeros个数的0可以组成count_ones * count_zeros个不同的数对每对数对对应一个汉明距离为1的位。因此该比特位上的总汉明距离就是count_ones乘以count_zeros。
