338. Counting Bits

Leetcode Dynamic Programming Bit Manipulation

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 1:

Input: 2
Output: [0,1,1]

Example 2:

Input: 5
Output: [0,1,1,2,1,2]

Follow up:

• It is very easy to come up with a solution with run time $O(n*\text{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.

分析

首先肯定是最直接的方法：依次求出每个数的二进制表示中1的个数，时间复杂度是$O(n\log n)$：

 public int[] countBits(int num) {
    int[] res = new int[num + 1];
    for (int i = 1; i < res.length; i++)
        res[i] = numbits(i);
    return res;
}

private int numbits(int num) {
    int count = 0;
    while (num > 0) {
        count += num & 1;
        num >>>= 1;
    }
    return count;
}

但是题目又说了，有没有更优的算法的时间和空间复杂度只有线性$O(n)$？既然只有线性，肯定是只有遍历一遍了，而且肯定需要利用前面的结果，也就是说很有可能利用到动态规划。设想一下当前数字$i$的二进制表示中有$k$位数，那么最低$k-1$位数的增加过程其实已经出现在前面增加的过程中，只不过最高位--第$k$位多了一个1而已。为了尽一步验证，尝试把最直接方法得到的res打印出来

for (int i = 0; i < res.length; i++) {
    if (res[i] == 1) System.out.println("\n");
    System.out.print(String.format("(%d)%2d, ", i, res[i]));
}
System.out.println("\n");

结果如下：

(0) 0, 
(1) 1, 
(2) 1, (3) 2, 
(4) 1, (5) 2, (6) 2, (7) 3, 
(8) 1, (9) 2, (10) 2, (11) 3, (12) 2, (13) 3, (14) 3, (15) 4, 

证明猜想是对的。那么代码的思路非常明显了：第$k$排数字等于前面的所有数字加1!

public int[] countBits(int num) {
    int[] res = new int[num + 1];
    for (int i = 1, row = 1, j = 0; i < res.length; i++) {
        if (i == row) { row *= 2; j = 0; }
        res[i] = res[j++] + 1;
    }
    return res;
}

后来在论坛上发现同样简单的方法：

f[n] = f[n去除最后一位数字] + 最后一位数字
f[i] = f[i >> 1] + (i & 1)

用代码表示为：

public int[] countBits(int num) {
    int[] f = new int[num + 1];
    for (int i=1; i<=num; i++) f[i] = f[i >> 1] + (i & 1);
    return f;
}