Problem description
https://leetcode-cn.com/problems/total-hamming-distance/
Solution
一开始直接暴力 O(n^2)果然超时了, 横向逐个比较行不通,换成竖的试试。
2 : 0010
4: 0100
14: 1110
海明码距离指的是两个数字的二进制数对应位不同的数量,竖着理解为 第i位 有 x 个 1,y 个 0,其不同的数量为 x * y, 以第三位为例,分别是 0,0,1。1个 1,两个 0。 其不同的数目为2。
我们需要一个 30位的数组去记录每一位的 1 的数目,因为题目中最大的数为 2^30,时间复杂度为 O(N * lgC) C 为数组中最大的数。空间复杂度为O(lgC)
r对于横向比较走不下去时,可以尝试从竖向出发进行解决问题。类似的还有多链表合并的那道题目
Code
1 | class TotalHammingDistance { |