首页 🍒LeetCode,🐶算法

题目

FcoOxoFUFI.png

思路

可以用__builtin_popcount求出数中二进制1的个数。但是暴力法会超时。

求出nums数组中各个数的第i位中1的个数n,0的个数m。
那么nums数组中每个数第i位的距离就是n * m。
然后每一位的距离都求出来累加就是答案。

求nums数组中第i位中1的个数可以右移(i - 1)位然后&1。
因为数据小于int的范围,所以最大32位。

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int n = 0;
            for (int j = 0; j < nums.size(); j++) {
                if ((nums[j] >> i) & 1 == 1) n++;
            }
            res += n * (nums.size() - n);
        }
        return res;
    }
};



文章评论