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:
- You should make use of what you have produced already.
- Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
- 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 递减，若出现了未记录的数，则继续如上的计算。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
/** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ int* countBits(int num, int* returnSize) { int *result,i,j,temp=0; *returnSize=num+1; result=(int *)malloc(*returnSize*sizeof(int)); for(i=0;i<*returnSize;i++) { result[i]=0; } for(i=num;i>=0;i--) { if(result[i]!=0) { continue; } else { temp=i; for(j=0;j<8*sizeof(int);j++) { if(temp&1) { result[i]++; } temp=temp>>1; } temp=i; j=0; while(temp!=0) { if(temp&1) { j++; } temp=temp>>1; result[temp]=result[i]-j; } temp=i; j=1; while(temp!=0) { temp-=(temp&-temp); result[temp]=result[i]-j; j++; } } } return result; } |