专栏首页眯眯眼猫头鹰的小树杈leetcode477. Total Hamming Distance

leetcode477. 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:
1. Elements of the given array are in the range of 0 to 10^9
2. Length of the array will not exceed 10^4.

计算N个数字之间的汉明码距离之和。 汉明码是指两个数字的二进制表示形式中,在对应位置上值不同的数量总和。如2和4,4的二进制表达式为100, 2的二进制表达式010,则二者在第二位和第三位的值不同,因此汉明码值为2。

思路和代码

如果直观的采用两两比较来得出任意两个数字之间的汉明码值,再将汉明码值的和进行累加,得出最终的汉明码值总和,则需要O(n^2)的时间复杂度。除此以外,还要乘上数字二进制的平均长度。

那么有没有方法能够尽可能的减少重复比较的场景。既然水平的以两个数字直接开始比较会超时,不如垂直的进行比较,即每次都比较同一位置上的所有二进制数值,假设一共有n个数字,其中有m个数字在第i上值为1,则剩下的n-m个数字在第i上的值为0。由此可知,在第i为上存在的(m-n)*n个数值不同的情况。对32位整数重复执行这个过程并累加即可得出最终的汉明码和。

代码如下:

    public int totalHammingDistance(int[] nums) {
         int count = 0;
         int length = nums.length;
         for(int i = 0 ; i<32 ; i++) {
               int countOfOne = 0;
               for(int j = 0 ; j < length ; j++) {
                   countOfOne += (nums[j] >> i) & 1;
               }
               count += countOfOne * (length - countOfOne);
         } 
         return count;
     }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode501. Find Mode in Binary Search Tree

    Given a binary search tree (BST) with duplicates, find all the mode(s) (the most...

    眯眯眼的猫头鹰
  • leetcode463. Island Perimeter

    用一个二维数组来表示一块岛屿的土地情况,其中1代表土地,0代表海洋。要求计算出岛屿的周长。题目中特别强调了不存在内陆湖的存在,其实是变相的降低了题目的难度。即我...

    眯眯眼的猫头鹰
  • leetcode502. IPO

    Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

    眯眯眼的猫头鹰
  • POJ2488-A Knight's Journey(DFS+回溯)

    题目链接:http://poj.org/problem?id=2488 A Knight's Journey Time Limit: 1000MS ...

    llhthinker
  • HDU-1011 Starship Troopers(树形dp)

    Starship Troopers Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536...

    ShenduCC
  • 多语种机器翻译: 缩小共享和特定语言编码解码器之间的差距(CS CL)

    最先进的多语种机器翻译依赖于通用的编码解码器,这需要重新训练整个系统来添加新的语言。 在本文中,我们提出了一种基于特定语言编码解码器的替代方法,从而可以更容易地...

    用户7095611
  • 【编程练习】poj1068

    Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in...

    用户1539362
  • POJ-2181 Jumping Cows(贪心)

    Jumping Cows Time Limit: 1000MS Memory Limit: 65536K Total Submissions:...

    ShenduCC
  • POJ 3461 kmp

    Oulipo Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 40168 ...

    attack
  • Codeforces 626E Simple Skewness(暴力枚举+二分)

    E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券