题目

两个整数的指的是这两个数字的二进制数对应位不同的数量。

给你一个整数数组 nums，请你计算并返回 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 <= 10⁵

0 <= nums[i] <= 10⁹

# 思路分析这个题一看就是勾我们上套。众所周知，求两个数字的汉明距离非常简单，直接求这两个数字异或之后的二进制位为1的数量即可，但是这个题目需要我们求的是所有数字之间互相的汉明距离，这就需要我们思考了。如果我们按照之前的方法来做，复杂度会居高不下，达到了$O(10^{5^2})$也就是$O(10^{10})$的复杂度，基本上是不可能做的出来的。那么怎么办呢题目给我们的示例，我们仔细地分析一下。数字|二进制位|1|2|3|4 --| 4||0|1|0|0 14||1|1|1|0 2||0|0|1|0 通过观察可以得出，**对于每一位二进制位上的汉明距离是可以分开讨论的**。对于1号位，也就是2^3位，分别是"0,1,0"，那么我们可以说，这三个数字在这个位置上的汉明距离是2*1等于2，因为有两个零和一个一。同理，2号位的汉明距离等于2\*1,三号位等于2\*1，四号位等于0。总和等于6，是否跟题目中计算的相等呢？ **所以我们就可以将求汉明距离总和改变成一个统计问题。也就是针对特定的位，我们统计其上有多少个1，多少个0，用1的数量乘以0的数量，这就是这个特定位的汉明距离。** 有了这个思路以后，问题就迎刃而解了。我们对于30个二进制位，分别统计，每一个位置上的0的数量和1的数量，并且将之相乘，加和到最终的答案里。 ### C++代码 ```cpp class Solution { public: int totalHammingDistance(vector& nums) { int res = 0;

for (int i = 0; i < 30; ++i) {        int zeros = 0, ones = 0, tmp = 1 << i;        for (auto num : nums) {            if (tmp & num) ones++;            else zeros++;        }        res += zeros * ones;    }    return res;}

};

### Rust代码```rustimpl Solution {    pub fn total_hamming_distance(nums: Vec
   
    ) -> i32 {        let mut ret = 0;        for i in 0..30 {            let mut zeros = 0;            let mut ones = 0;            for num in &nums {                match (1 << i) & num {                    0 => zeros += 1,                    _ => ones += 1,                }            }            ret += zeros * ones;        }        ret    }}

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

你可能感兴趣的文章