LeetCode 338 - Counting Bits

作者 QIFAN 日期 2016-12-21
LeetCode 338 - Counting Bits

原题链接:338. Counting Bits


题目

给定一个数字 n ,计算 0 ~ n 二进制形式中的 1 的个数。并以数组形式返回结果。

举例:n = 5
返回:[0,1,1,2,1,2]

思路

思路 1 Brute Force

将每个数转成二进制,一个一个数。
时间复杂度 $O(nlogn)$,空间复杂度 $O(n)$

思路 2 奇数偶数

简单粗暴的方式很容易想到,但是每个数的计算间都很独立,如果可以将他们间建立联系?

对于偶数,其二进制的末尾肯定是0,因此它的下一个数(奇数)的 1 只需比前一个偶数的 1 多 1。
对于奇数,要考虑到进位。比如:
1 + 1 = 10
11 + 1 = 100
111 + 1 = 1000

也就是说,末尾连续的 “1” 最后变成了 1 个。所以 1 的变化应该是(前一个(偶数)的 1 - 末尾连续 1 + 1)

如何计算连续 1 ?
位运算不是很熟,我只能想到不断将奇数 i 右移,直到变成偶数 j(末尾变成 0)。

这又让我想到,j 必然比 i 小,所以 j 我们肯定也已经计算过了,所以 i 中 1 的个数就是 j 中 1 的个数加 1 。

如此思路就很清晰了。

分析:对于每个奇数,需要 1 步计算,对于每个偶数 i ,最多需要 $log(n)$。比 $O(nlogn)$ 小

代码:

public class Solution {
public int[] countBits(int num) {
int[] result = new int[num + 1];
result[0] = 0;
for (int index = 0; index < num; index++) {
int temp = index;
while (temp >> 1 << 1 < temp) {
temp = temp >> 1;
}
result[index + 1] = result[temp] + 1;
}
return result;
}
}