LeetCode(338) 比特位计数

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

本题来自LeetCode:338. 比特位计数,

题目内容

给定一个非负整数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)来执行此操作。

题目分析

本题明显可以使用暴力法解答出来,对每个数值采用位移法统计,但是时间复杂度为O(n*sizeof(integer)),不满足进阶的要求。
定义bits[n]为值num的比特位1的个数。
初步分析,没有什么头绪。故先手工计算下前面几个数字,期望能够发现些规律:

num 二进制 bits[num]
0 00000000 0
1 00000001 1
2 00000010 1
3 00000011 2
4 00000100 1
5 00000101 2
6 00000110 2
7 00000111 3
8 00001000 1

从上面的表格中,显然可以发现,值为2的n次方时,比特位1的个数为1,即 bits[2^n] = 1;将上面的分析的结果继续拆分:

num 二进制 bits[num] 表达式
0 00000000 0 0 bits[0]
1 00000001 1 2^0 bits[1]
2 00000010 1 2^1 bits[2]
3 00000011 2 2 + 1 bits[2] + bits[1]
4 00000100 1 2^2 bits[4]
5 00000101 2 2^2 + 1 bits[4] + bits[1]
6 00000110 2 2^2 + 2 bits[4] + bits[2]
7 00000111 3 2^2 + 3 bits[4] + bits[3]
8 00001000 1 2^3 bits[8]

现在规律已经非常明显了,可通过动态规划来解答此题。当num不为2的n次方时,比特位1的个数为bits[num] = bits[2^n] + bits[num - 2^n],其中2^n < num < 2^(n+1)

添加解答

整理以上分析,完整的解答过程如下:

class Solution {
public int[] countBits(int num) {
int[] bits = new int[num + 1];
if(num == 0) {
return bits;
}
bits[1] = 1;
int temp = 1; // 记录2的n次方
for(int i = 2; i <= num; i ++) {
// 若i是2的次方,直接设置为1
if(temp << 1 == i) {
temp <<= 1;
bits[i] = 1;
} else {
bits[i] = bits[temp] + bits[i - temp];
}
}
return bits;
}
}


原文始发于微信公众号(xiaogan的技术博客):LeetCode(338) 比特位计数