Leetcode-338 Counting Bits

发表于 | 分类于 | 次

Counting Bits

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.

Follow up:

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

Example 1

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

Example 2

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

解题思路

法一：从 1 开始，遇到奇数 i，其值为 res[i/2]+1，遇到偶数 i，其值为 res[i/2]。

法一：从 1 开始，res[i]=res[i&(i-1)]+1。另外，i&(i-1) 为零可判断 i 为 2 的幂。

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$，存储结果需要。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
	vector<int> countBits(int num) {
		vector<int> res(num + 1, 0);

		// 法一
		for (int i = 1; i <= num; ++i) {
			res[i] = i % 2 ? res[i / 2] + 1 : res[i / 2];
		}

		// 法二
		for (int i = 1; i <= num; ++i) {
			res[i] = res[i&(i - 1)] + 1;
		}

		return res;
	}
};

参考

[LeetCode] Counting Bits 计数位