描述
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
示例 2:
进阶:
- 给出时间复杂度为
O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
- 要求算法的空间复杂度为
O(n)。
- 你能进一步完善解法吗？要求在C或任何其他语言中不使用任何内置函数（如 C 中的
__builtin_popcount）来执行此操作。
来源：力扣（LeetCode）
链接：338. Counting Bits
解题思路
对于时间复杂度为O(n*sizeof(integer))的解法没有特别需要说，相当于暴力解法。显然，返回数组的个数为num + 1，新建一个int型指针变量result，然后用malloc函数动态分配空间。
代码本身主要做的事情就是遍历0 ≤ i ≤ num ，对于每一个i都计算其二进制数中的1的数目并将它们赋值给result，最后返回。
具体代码可以见解法一。
不过，既然题目要求要在O(n)的时间复杂度之内完成，那么其中必然有一些规律。
我们首先把0到15的数的二进制和1的个数写出来：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 0 0000 0
-------------
1 0001 1
-------------
2 0010 1
3 0011 2
-------------
4 0100 1
5 0101 2
6 0110 2
7 0111 3
-------------
8 1000 1
9 1001 2
10 1010 2
11 1011 3
12 1100 2
13 1101 3
14 1110 3
15 1111 4
|
通过观察得出的规律是，从1开始，遇到偶数时，其1的个数和该偶数除以2得到的数字的1的个数相同，遇到奇数时，其1的个数等于该奇数除以2得到的数字的1的个数再加1，具体代码见解法二。
如果能够巧妙的使用i & (i - 1)，这个本来是用来判断一个数是否是2的指数的快捷方法，比如8，二进制位 1000, 那么 8 & (8 - 1) 为0，只要为0就是2的指数, 那么我们现在来看一下0到15的数字和其对应的 i & (i - 1) 值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| i binary '1' i&(i-1)
0 0000 0
-----------------------
1 0001 1 0000
-----------------------
2 0010 1 0000
3 0011 2 0010
-----------------------
4 0100 1 0000
5 0101 2 0100
6 0110 2 0100
7 0111 3 0110
-----------------------
8 1000 1 0000
9 1001 2 1000
10 1010 2 1000
11 1011 3 1010
12 1100 2 1000
13 1101 3 1100
14 1110 3 1100
15 1111 4 1110
|
我们发现，每个i对应二进制当中1的数量都是i & (i - 1)对应的加1，具体代码见解法三。
代码
解法一
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
|
int countOne(int n)
{
int count = 0;
while(n)
{
count++;
n &= (n-1);
}
return count;
}
int* countBits(int num, int* returnSize)
{
*returnSize = num + 1;
int* result = (int *)malloc(sizeof(int) * (num + 1));
for(int i = 0; i <= num; i++)
{
result[i] = countOne(i);
}
return result;
}
|
解法二
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
|
int* countBits(int num, int* returnSize)
{
*returnSize = num + 1;
int* result = (int *)malloc(sizeof(int) * (num + 1));
result[0] = 0;
for(int i = 1; i <= num; i++)
{
if(i % 2 == 0)
{
result[i] = result[i/2];
}
else
{
result[i] = result[i/2] + 1;
}
}
return result;
}
|
解法三
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
int* countBits(int num, int* returnSize)
{
*returnSize = num + 1;
int* result = (int *)malloc(sizeof(int) * (num + 1));
result[0] = 0;
for(int i = 1; i <= num; i++)
{
result[i] = result[i & (i - 1)] + 1;
}
return result;
}
|
参考