LeetCode 338 Counting Bits

比特位计数

题意

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

示例 1:

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

示例 2:

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

解法

此题是 LeetCode 191 Number of 1 Bits 的拓展版, 可以利用那道题的两种算法, 只不过套个循环, 时间和空间复杂度都是 O(n).

那两种解法就不说了. 这里说下另一种解法.

这里分为 2 的倍数非 2 的倍数 两种数.

他们有一个区别就是二进制的最低位是否为 1.

2 的倍数其二进制最低位都是 0.
非 2 的倍数其二进制最低位都是 1.

除 2 或右移一位后, 等于是去掉最低位, 那么既然 2 的倍数最后一位都是 0, 所以对于 2 的倍数 除 2 或右移一位后, 数字 1 的个数并不会变.

那么对于非 2 的倍数 n, n 肯定比 n - 1 的二进制中 1 的个数多一位. 如 n = 1111, n - 1 = 1110.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int[] countBits(int num) {
int[] arr = new int[num + 1];
for (int i = 0; i <= num; i++) {
if (i % 2 == 0) {
arr[i] = arr[i >> 1];
} else {
arr[i] = arr[i - 1] + 1;
}
}
return arr;
}
}

时间复杂度 O(n), 空间复杂度 O(n).

  • 本文作者: 赵俊
  • 本文链接: http://www.zhaojun.im/leetcode-338/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!