题目
给定一个非负整数 num。 对于范围 0 ≤ i ≤ num 中的每个数字 i ,计算其二进制数中的1的数目并将它们作为数组返回。
示例:
比如给定
num = 5
,应该返回
[0,1,1,2,1,2]
.
进阶:
给出时间复杂度为
O(n * sizeof(integer))
的解答非常容易。 但是你可以在线性时间O(n)内用一次遍历做到吗?
要求算法的空间复杂度为
O(n)
。
你能进一步完善解法吗? 在c ++或任何其他语言中不使用任何内置函数(如c++里的
__builtin_popcount
)来执行此操作。
题解
这道题可以考虑
n=n-1+1
,那么对于
n-1
最低位为
的时候,
n
的
1
的个数就等于
n-1
的
1
的个数加
1
。
但是如果
n-1
最低位不为
1
,那么加
1
之后,原先低位为
1
的由于进位都变成
,从最右侧往左第一个
的位置变为
1
;所以
n
中
1
得个数就等于
n-1
中
1
的个数减去
n-1
最低位连续
1
的个数加上
1
。
例如:
1=1(2) 1 = 1 ( 2 ) 2=10(2) 2 = 10 ( 2 ) 3=11(2) 3 = 11 ( 2 ) 4=100(2) 4 = 100 ( 2 )
代码
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res;
res.push_back(0);
for(int i=1;i<=num;i++){
if(((i-1)&1)==0){
res.push_back(res[i-1]+1);
continue;
}
for(int j=0;j<32;j++){
if(((i-1)&(1<<j))==0){
res.push_back(res[i-1]-j+1);
break;
}
}
}
return res;
}
};