【Day32】477.汉明距离总和

477. 汉明距离总和

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

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

示例:

输入: 4, 14, 2

输出: 6

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

注意:

  • 数组中元素的范围为从 0到 10^9。
  • 数组的长度不超过 10^4。

题解:

class Solution {
public:
    int totalHammingDistance(vector& nums) {
        int ans = 0;
        for (int i = 0; i < 31; i++) {
            int cnt[]  = {0, 0};
            for (auto& num : nums) {
                cnt[num & 1]++;
                num >>= 1;
            }
            ans += cnt[0] * cnt[1];
        }
        return ans;
    }
};

   转载规则


《【Day32】477.汉明距离总和》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day33】1074.元素和为目标值的子矩阵数量 【Day33】1074.元素和为目标值的子矩阵数量
1074. 元素和为目标值的子矩阵数量给出矩阵 matrix 和目标值 target,返回元素总和等于目标值的非空子矩阵的数量。 子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y
2021-05-29
下一篇 
【Day31】461.汉明距离 【Day31】461.汉明距离
461. 汉明距离两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。 给出两个整数 x 和 y,计算它们之间的汉明距离。 注意: 0 ≤ x, y < 231. 示例: 输入: x = 1, y = 4 输出:
2021-05-27
  目录