一、题目

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中，任意两个数之间汉明距离的总和。

点击查看原题

二、思路

数字的每一位上的汉明距离和其他位不相关，只需统计出不同元素同一位的1的个数n，就可以制度这位的总共汉明距离：n*(nums.length - n)。

三、代码

  1. class Solution {
  2.     public int totalHammingDistance(int[] nums) {
  3.         int[] memo = new int[32];
  4.         for (int num : nums) {
  5.             for (int i = 0; i < memo.length; i++) {
  6.                 memo[i] += ((num >> i) & 1);
  7.             }
  8.         }
  9.         int ans = 0;
  10.         for (int i = 0; i < memo.length; i++) {
  11.             ans += memo[i]*(nums.length - memo[i]);
  12.         }
  13.         return ans;
  14.     }
  15. }

空间复杂度位O(n)，时间复杂度为O(32*n)。空间复杂度可以进行优化，此处不作优化。