477.汉明距离总和

题目

原题 477.汉明距离总和

题解

直接使用暴力方法计算 total hamming distance 会超时:

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res =0;
        for (int left =0; left< nums.length; left++){
            for (int right = left+1; right<nums.length; right++){
                res += hammingDistance(nums[left], nums[right]);
            }
        }
        return res;
    }
    
    public int hammingDistance(int left, int right){
        int xor = left^right;
        int res =0;
        while (xor!=0){
            if ((xor&1)==1){
                res++;
            }
            xor >>=1;
        }
        return res;
    }
}

实际上题目中给出了提示，每个整数都是 32 bit，可以依次统计每一个 bit 位置上的 hamming distance，最终将它们加和作为最终结果。 假设考虑 i 位置的 bit，可以统计出来有多少数字在这个位置上是 1 (count_1)，剩下的就都是 0 (count_0)，下面是 i 位置的 hamming distance:

sum_distance[i] = count_1 * count_0

下面是改进之后的代码:

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res =0;
        for (int bitIdx =0; bitIdx<32; bitIdx++){
            int bit = 1<<bitIdx;
            int one = 0;
            for (int num: nums){
                if ((num&bit)!=0){
                    one++;
                }
            }
            res+=(one * (nums.length-one));
        }
        return res;
    }
}