专栏首页二进制文集LeetCode 477 Total Hamming Distance

LeetCode 477 Total Hamming Distance

题目描述

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note: Elements of the given array are in the range of 0 to 10^9 Length of the array will not exceed 10^4.

题目分析

此题和第 461 题很像,初看是 461 题目的延伸。按照那道题的思路来做就是:

  1. 对数组中所有的数进行两两组合
  2. 对于每两个数的组合,求一次 Hamming Distance

但是这样做会超时,是因为两两组合的时间复杂度是 O(n^2),而求一次组合也需要最多 32 次循环。

那么应该怎么做这道题目呢?题目中的 Explanation 其实是一种误导,我们真的有必要两两组合分别求 Hamming Distance 吗?其实是没有必要的,一次循环能否取得所有的 Hamming Distance?

通过分析得出,Hamming Distance 其实就是每一位的异同。那么这道题目就可以转化为:求x个数每两个数的组合中,每一位的异同数量。想到这里,就会发现其实x个数中每个数的数值并不重要,重要的是每一位有多少个0和多少个1。

假设有x个数中,第一位有m个0,n个1,则该位的Hamming Distance 是:m * n。

代码

public int totalHammingDistance(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }
    
    int[] m = new int[31];// 存储对应位数,有多少个0
    for(int num : nums) {
        for(int i = 0; i < 31; i++) {
            if ((num & (1 << i)) == 0) {
                m[i]++;
            }
        }
    }
    
    int result = 0;
    for(int i = 0; i < 31; i++) {
        result += m[i] * (nums.length - m[i]);
    }
    
    return result;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 401 Binary Watch

    A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6...

    Yano_nankai
  • LeetCode 949 Largest Time for Given Digits

    Given an array of 4 digits, return the largest 24 hour time that can be made.

    Yano_nankai
  • Java 八大排序实现

    将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序...

    Yano_nankai
  • LeetCode Weekly Contest 47解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 【USACO 3.2】Magic Squares

    4*2个格子分别为 1234 8765 的魔板有3种操作,A:上下两排互换,B:最后一列放到第一列前面,C:中间四个顺时针旋转1格。 现在给出目标状态,...

    饶文津
  • 弱校联盟10.3

    n对括号最多需要1+2+..+n次交换,当它是)))..(((的形式时,)))(((需要6次,然后把中间两个交换一下,))()((就还需要5次,再交换一次靠近左...

    饶文津
  • 1466: [蓝桥杯2019初赛]等差数列

    数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中N 个整数。现在给出这N 个整数,小明想知道包含这N 个整数的最短的等差数...

    可爱见见
  • Leetcode 75 Sort Colors

    Given an array with n objects colored red, white or blue, sort them so that obj...

    triplebee
  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack
  • 1545 最简单排序

    个人博客:double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

    attack

扫码关注云+社区

领取腾讯云代金券