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].

Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Hint:

  1. You should make use of what you have produced already.
  2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
  3. Or does the odd/even status of the number help you in calculating the number of 1s?

一开始没看 Hint ,看到题目的要求下意识的想到了树状数组中 lowbit 的用法,但是感觉这样还是不能满足 O(N) 的时间要求……

思路大体是这样的,首先从 num 开始计算出 1 的个数,然后通过形似 num-=(num&-num) 的运算消去最后一个 1 ,完成对下一个 num 的计数,然后依次类推。之后从 num 递减,若出现了未记录的数,则继续如上的计算。

代码如下:

 

发表评论

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