[LeetCode 338] Counting Bits

作者 Shilei Tian 日期 2016-04-26
[LeetCode 338] Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].

题目的意思很简单,就是给定一个数字 num,输出从 0 到 num 所有数字的二进制表示中数字 1 的个数,并给出了一个例子。
拿到这个题,这该怎么做呢?简单的利用求余运算来计算?可以,但是那样的话时间复杂度比较高,有没有什么比较高效的算法?下面来说一个思路,看下下图:

1-7 二进制示例

这个图是 1-7 二进制的表示,为什么要画一条黄色的线呢?观察到,这条黄线把这个二进制位拆成两部分,左边部分是一个二进制数字 a1,右边部分就是一个二进制位 a2,那么我们自然可以想到,a2 = n % 2,这里 n 表示任一正整数,a1 = n >> 1。那么每一个数 n 的二进制 1 的个数可以表示成 r(n) = r(a1) + a2,这里 r(n) 表示数字 n 对应二进制表示中 1 的个数。并且,显然 a1 >> 1 <= a1,就是一个数右移一位肯定小于等于它自己。所以,我们就可以迭代一次即可得到最终的结果。具体的代码如下:

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
vector<int> countBits(int num) {
vector<int> ret(num + 1, 0);
for (int i = 1; i <= num; ++i) {
ret[i] = ret[i >> 1] + i % 2;
}
return ret;
}
};