本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目描述

二、解题思路

leetcode每日一题，今天是汉明距离升级版。
昨天我们已经学会了计算汉明距离

1.逐位统计

如果我们两两计算一对数字的汉明距离，那时间复杂度为O(n^2logn).
那有没有复杂度更低的算法呢？？
答案是可以的：

对于数组nums 中的某个元素 val，若其二进制的第 i 位为 1，我们只需统计 nums 中有多少元素的第 i 位为 0， 
即计算出了val 与其他元素在第 i 位上的汉明距离之和。具体地，若长度为n 的数组nums 的所有元素二进制的第i  
位共有 c 个 1，n−c个0，则些元素在二进制的第 i 位上的汉明距离之和为：
                    c⋅(n−c)
复制代码

代码实现

class Solution {
    public int totalHammingDistance(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 0; i < 30; ++i) {
            int c = 0;
            for (int val : nums) {
                c += (val >> i) & 1;
            }
            ans += c * (n - c);
        }
        return ans;
    }
}
复制代码