题目描述

[EN | CN]

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

1
2
输入: 2
输出: [0,1,1]

示例 2:

1
2
输入: 5
输出: [0,1,1,2,1,2]

进阶:

  • 给出时间复杂度为 $O(n*\operatorname{sizeof}(\text{integer}))$ 的解答非常容易。但你可以在线性时间 $O(n)$ 内用一次扫描就做到吗?
  • 要求算法的空间复杂度为 $O(n)$。
  • 你能进一步完善解法吗?要求在C++或任何其他语言中不使用任何内置函数(如 C++ 中的 __builtin_popcount)来执行此操作。

解法 1:动规

我们要计算每个数字 i 的二进制数中的 1 的个数,其实它等于 i % 2 中 1 的个数加上 i / 2 中 1 的个数

举个例子,对于二进制数 1001 1101 来说,我们要计算 1 的个数,其实相当于计算 1001 1100(即 i / 2)、0000 0001(即 i % 2)中的 1 的个数之和。

因此,我们基于动规的思想,依次计算。

假设数字为 $n$,那么

  • 时间复杂度为 $O(n)$,线性时间;
  • 空间复杂度为 $O(n)$,保存结果。

实现与结果如下:

1
2
3
4
5
6
7
8
class Solution:
    def countBits(self, num: int) -> List[int]:
        ret = [0, 1]
        if num <= 1:
            return ret[:num + 1]
        for i in range(2, num + 1):
            ret.append(ret[i // 2] + ret[i % 2])
        return ret
  • 执行用时:88 ms,在所有 Python3 提交中击败了 88.73% 的用户。
  • 内存消耗:20.5 MB,在所有 Python3 提交中击败了 11.11% 的用户。