Counting Bits 「LeetCode-388」

836 阅读5分钟

题目

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: For num = 5
you should return [0,1,1,2,1,2]

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.

这个题目大意是给定一个非负数num, 然后让我们计算0~num之间每一个数字的二进制表示中1的个数并以数组的形式返回。其中要求时间复杂度和空间复杂度均为O(n)。

失败的解决案例

看到这个题目时,我第一时间想到的解决方案是:

  1. 第一步毋庸置疑,一定是对0~num进行遍历,至于是for还是while循环都可以。
  2. 循环体中的操作
    • 将数字转换为二进制字符串 num.toString(2)
    • 对二进制字符串进行遍历,这里使用通用的for...in还是Object.keys()都可行。不过这里我们采用的是先用空串分割转换为数组之后,就可以直接使用数组的forEach方法进行遍历操作了
    • 使用临时变量在循环体中对当前数字中1的个数进行统计,然后push进数组即可。

Code

function countBits (num) {
    if (!num && num !== 0) return
    let result = []
    while (num >= 0){
        let count = 0
        num.toString(2).split('').forEach(a => a === '1' && count++)
        result.unshift(count)
        num--
    }
    return result
}

不知大家有没有发现,该solution的时间复杂度因为两层的嵌套循环使得时间复杂度已经超越O(n^2)了, 由于里层循环的次数与n含有函数关系,暂且把它当作是O(n^2)的复杂度吧 ! 结果可想而知,在OJ过程中没有被Accept......

思考 : 现在问题来了,如果要把时间复杂度控制在O(n)上,就意味着在外层必须要的循环里,要保证内层操作的时间复杂度为O(1),也就意味着内层不能用循环来处理。

百思不得解后,很没出息的翻开了Hint提示,如下:

  1. You should make use of what you have produced already.
  2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
  3. Or does the odd/even status of the number help you in calculating the number of 1s?
  1. 你应该利用已经计算出的部分结果
  2. [2-3], [4-7], [8-15] 以这个区间的形式对数字进行划分,并且尝试对前边已经利用过的数据进行重新分组
  3. 或者也可以对数字的奇偶性切入判断

官方建议解法一

分析:

第二条中讲到对数字进行分组,我们先通过js程序将0~32之间的数字的二进制值打印一下,分析一下结构规律:

0:      0000    0001   
2:      0010    0011
4:      0100    0101     0110     0111
8:      1000    1001     1010     1011    1100    1101    1110    1111
16:    10000...

将数据按照2的次幂分组后,发现每逢二的次幂,该行的数据全部跟前边若干行的数据有关,具体如下:



总结上图规律:

  1. 每行开头的值都是2的次幂,这意味着发生了总位数的增加。因为固定二进制位数能表示的范围是0~2^n-1。在最高位加了1后,后半部分(当前行)值的增长本质上是对前半部分的复制,也就是说抛开增长的最高位,后边的几位数盒前半部分值是完全相同的。
  2. 由此推断出当前行每一个数字中1的位数都比前半部分所对应的数字多1个(最高位)
  3. 我们只要抓准当前行的开始值,然后对前几行的数据从0开始记录,直到最后一个数字,依次加一即可完成对当前数字中1个数的推算。

Code:

function countBits (num) {
    let result = [0];
    let pow = 1
    for(let i = 1, t = 0; i <= 1="" num;="" i++,="" t++)="" {="" if(i="=" pow)="" 抓取是否是行首值="" pow="" *="2" t="0" 对前半部分的纪录游标置零="" }="" result[i]="result[t]" +="" 对当前遍历中的每一个元素+1="" return="" result="" }

直接看代码可能还是有难度的,通过分析之后,发现还是非常通读易懂的。

官方建议解法二

本解法的途径则是根据数字的奇偶性来作为切入点

分析

  1. 妇孺皆知,偶数后必然是奇数,也就是最后一个二进制位是1,前几位都一样。
  2. 对一个偶数除2取整,则可以计算出与之对应1个数相同的数。这样不好理解也可以利用>>位运算的方式增强理解。对一个偶数(最低位为0)向右移动一位(除二)可以推理出与之相同1个数的数;对于奇数而言,其1个数的统计只比前一个大1。
  3. 列计算式: re[i] = re[i / 2] + i % 2
    Code:
    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;
     }
    小记
    1. 这里的运算方式中,取余时采用了'&',位运算的乘法,这也是取出最低位数字(余数)的一种较为简便的方
      式。
    2. 由于Javascript中没有取整运算,因此如果用Javascript作为语言的话,如果不用位运算,就得要用以下几种函数了:
      • Math.floor(num) 向下取整
      • Math.ceil(num) 向上取整
      • parseInt(num) 向下取整
      • Math.round(num) 四舍五入
      • num.toFixed(x) 选择保留小数位数,取值遵循四舍五入

总结:

  • 寻找规律
  • 利用双游标进行判断对比,第一个游标完成对前半部分的遍历,同时平行生成后半部分数据,从而达到O(n)的时间复杂度
  • Coding...