1. 问题
：给定一个非负整数
num
。对于
0 ≤ i ≤ num
范围中的每个数字
i
，计算其二进制数中 1 的数目，并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]示例 2:
输入: 5
输出: [0,1,1,2,1,2]
进阶:
-
给出时间复杂度为
O(n*sizeof(integer))
的解答非常容易。但你可以在线性时间
O(n)
内用一趟扫描做到吗？ -
要求算法的空间复杂度为
O(n)
。 -
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的
__builtin_popcount
）来执行此操作。
2. 分析：
已知0-19的二进制如下所示：
0
0000
1
0001
2
0010
3
0011
4
0100
5
0101
6
0110
7
0111
8
1000
9
1001
10
1010
11
1011
12
1100
13
1101
14
1110
15
1111
16
1 0000
17
1 0001
18
1 0010
19
1 0011 …..
由观察可得：
2^n
（n=0,1,2,3,….）的二进制中1的数量都为1，
3
的二进制中1的数量可以由
1和2
中1的数量之和得到，
5
的二进制中1的数量可以由
4和1
中1的数量之和得到，
6
的二进制中1的数量可以由
4和2
中1的数量之和得到，
7
的二进制中1的数量可以由
4和3
中1的数量之和得到，
9
的二进制中1的数量可以由
8和1
中1的数量之和得到，
…
15
的二进制中1的数量可以由
8和7
中1的数量之和得到, 因此可以通过逐步推理来得到结果
|
n |
0 | 1 | 2 | 3 | 4 | |||||||||||||
|
2^n |
num | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|
List |
0 |
1 |
1 |
2 |
1 |
2 | 2 | 3 |
1 |
2 | 2 | 3 | 2 | 3 | 3 | 4 |
1 |
2 |
3. 自己编写的代码：
def countBits(num):
if num ==0:
return [0]
if num == 1:
return [0,1]
n=0
for i in range(num+1): # 作用类似于 n=int(math.log(num,2))
if 2**i > num:
n = i - 1
break
print("n=",n)
List=[0,1,1]
for i in range(1,n): # n>=2, List只计算到2**n
for j in range(1,2**i):
List.append(1+List[j])
List.append(1) # num=4,8,16...时,List添加1
print("List",List)
if (num - 2**n) > 0: # 计算剩余的List
for i in range(1,(num - 2**n)+1):
List.append(List[i]+1)
return List
print(countBits(2))
4. 大神编写的代码：
def countBits(num):
ans = [0]
for x in range(1, num + 1):
ans += ans[x & (x - 1)] + 1, # & 按位与运算，注意“,”不要省略
return ans