比特位计数
题目描述
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例1:
输入: 2
输出: [0,1,1]
示例2:
输入: 5
输出: [0,1,1,2,1,2]
进阶:
题目来源:
剑指offer(专项突击版) [剑指offer|| 003]前n个数字二进制中1的个数
力扣官方338题
题解
为了表述简洁，下文用「一比特数」表示二进制表示中的 1 的数目。
解法一 暴力枚举
这是我最先想到的方法,两个循环暴力枚举直接出结果，但是这种方法的时间复杂度和空间复杂度都很高.
定义一个数组，将0~n进行遍历，将循环中的i转换成二进制字符串，然后将二进制字符串分割成数组chars，再对chars进行遍历，如果chars[j]=‘1’,sum++;遍历完之后将sum添加到数组中.
var countBits = function(n) {
let sum = 0;
let number = [];
for(let i=0;i<=n;i++ ){
let value = i.toString(2);
let chars = value.split('');
for(let j=0;j<chars.length;j++){
if(chars[j] == '1')
sum++;
}
number.push(sum);
sum=0;
}
return number
}
解法二 Brian Kernighan算法位运算
位运算&表示同1为1, 令x&(x-1),该运算将x的二进制表示的最后一个1变成0，因此，对 x 重复该操作，直到x变成0,则操作次数即为x的「一比特数],例如：令x=10，二进制表示位1010,(x-1)=9.二进制表示为1001,10&9=1000. 1000比1010少了一个1
对于给定的 n，计算从 0 到 n 的每个整数的「一比特数」的时间都不会超过 )O(logn)，因此总时间复杂度为 O(nlogn)。
var countBits = function(n) {
const bits = new Array(n+1).fill(0)
for(let i=0;i<=n;i++){
let num = getNumOne(i);
bits[i] = num;
}
return bits;
}
var getNumOne = function (n){
let x=0
while(n>0){
n&=(n-1);
x++;
}
return x
}
时间复杂度😮(nlogn)。需要对从0到n的每个整数使用计算「一比特数」，对于每个整数计算 「一比特数」的时间都不会超过O(logn)。
空间复杂度😮(1)。除了返回的数组以外，空间复杂度为常数。
解法三 动态规划 位运算(最高有效位)
当计算 i 的「一比特数」时，如果存在 0 <=j<i，j 的「一比特数」已知，且 i 和 j 相比，i的二进制表示只多了一个 1，则可以快速得到 i 的「一比特数」。
上述关系可以表示成: bits[i]=bits[j]+1
对于正整数x，如果可以知道最大的整数y,使得y<=x并且y是2的整数次幂，则y的二进制表示中只有最高位是1，其余都是0，此时称 y 为 x 的「最高有效位」。令z=x-y,则bits[x]=bits[z]+bits[y]=bits[z]+1
为了判断一个正整数是不是 2 的整数次幂，可以利用方法二中提到的按位与运算的性质,如果y是2的整数次幂,则y&(y-1)=0;由此可见没正整数y是2的正整数次幂，当且仅当y&(y-1)=0
如果i&(i-1)=0,则令hignBit=i,更新当前的最高有效位
bits[i]=bits[i-hignBit]+1
const bits = new Array(n+1).fill(0);
let hignNum=0;
for(let i=1;i<=n;i++){
if((i&(i-1))==0){
hignNum = i;
}
bits[i] = bits[i-hignNum]+1;
}
return bits;
时间复杂度😮(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
空间复杂度😮(1)。除了返回的数组以外，空间复杂度为常数。
解法四 动态规划 位运算(设置最低位)
定义正整数 x 的「最低设置位」为 x 的二进制表示中的最低的 1 所在位，例如，10的二进制表示是1010，其最低设置位是2，二进制表示为10
令y=x&(x-1),则y为将x的最低设置位从1变成0之后的数，显然0<=y<=x,bits[x]=bits[y]+1,
对于任意正整数x，都有bits[x]=bits[x&(x-1)]+1
const bits = new Array(n+1).fill(0)
for(let i=1;i<=n;i++){
bits[i]=bits[(i&(i-1))]+1;
}
return bits;
时间复杂度😮(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
空间复杂度😮(1)。除了返回的数组以外，空间复杂度为常数。
解法五 动态规划 位运算(最低有效位)
对于正整数 x，将其二进制表示右移一位，等价于将其二进制表示的最低位去掉，得到的数是[x/2],如果bits[x/2]已知，则可以得到bits[x]的值
判断x的奇偶可以通过x&1得到，如果为奇数，x&1=1，反之为0
则 bits[x]=bits[x>>1]+(x&1)
const bits = new Array(n+1).fill(0);
for(let i = 1;i<=n;i++){
bits[i] = bits[i>>1]+(i&1)
}
return bits;
时间复杂度😮(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
空间复杂度😮(1)。除了返回的数组以外，空间复杂度为常数。
|