Leetcode每日一题——汉明距离总和

题目描述 两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

计算一个数组中，任意两个数之间汉明距离的总和。 示例

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

我理解的是一个组合的数学问题 从nums数组中任取两个，计算汉明距离，然后相加。直接暴力搞，时间复杂为 O ( n 2 ) O(n^2) O(n2)。但是将数字写成二进制表示，可以发现，整个数组的汉明距离之和是各个二进制位上的任意两个数不同的和。 所以可以统计整个数组每位上0和1的个数，然后根据组合，就是在0堆中选一个，在1堆中选一个构成的组合数量。 若0的个数为c，1就为n-c，结果就是 C ( c , 1 ) ∗ C ( n − c , 1 ) C(c,1)*C(n-c,1) C(c,1)∗C(n−c,1).

class Solution {
          
   
public:
    int totalHammingDistance(vector<int>& nums) {
          
   
        int n = nums.size();
        int res = 0;
        for(int i=0;i<30;i++){
          
   
            int c = 0;
            for(auto &t : nums){
          
   
                if(t>>i&1) c++;
            }
            res += c*(n-c);
        }
        return res;
    }
};

时间复杂度为 O ( n ∗ c ) O(n*c) O(n∗c) c=30