Total Hamming Distance–LeetCode#477

 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:

  1. Elements of the given array are in the range of to 10^9
  2. Length of the array will not exceed 10^4.

计算一个整型数组中的Hamming distance之和

/**
 * @Author: Poldi
 * @Date: 2018/3/30 下午3:17
 * @Description:
 */
public class TotalHammingDistance {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] != nums[j]){
                    res += HammingDistance(nums[i], nums[j]);
                }
            }
        }
        return res;
    }
    int HammingDistance(int a, int b) {
        int xor = a ^ b;
        int count = 0;
        while (xor > 0) {
            count += xor & 1;
            xor = xor >> 1;
        }
        return count;
    }
    public static void main(String[] args) {
        TotalHammingDistance totalHammingDistance = new TotalHammingDistance();
        int[] nums = {4, 14, 4};
        System.out.println(totalHammingDistance.totalHammingDistance(nums));
    }
}

用了最最最无脑的思路,两次循环计算每组数字之间的Hamming distance求和,超时…时间复杂度为O(n2)
借鉴大神的思路,计算所有数字同一个bit位上1出现的次数count,这一位上的Hamming distance为 count * (nums.length – count),然后计算所有bit位上的1数量求和。

/**
 * @Author: Poldi
 * @Date: 2018/3/30 下午3:17
 * @Description:
 */
public class TotalHammingDistance {
    private int totalHammingDistance(int[] nums) {
        int total = 0, n = nums.length;
        for (int j=0;j<32;j++) {
            int bitCount = 0;
            for (int i=0;i<n;i++)
                bitCount += (nums[i] >> j) & 1;
            total += bitCount*(n - bitCount);
        }
        return total;
    }
    public static void main(String[] args) {
        TotalHammingDistance totalHammingDistance = new TotalHammingDistance();
        int[] nums = {4, 14, 4};
        System.out.println(totalHammingDistance.totalHammingDistance(nums));
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注