剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

60 阅读 0 评论 40 点赞

我是靠谱客的博主魁梧背包，最近开发中收集的这篇文章主要介绍剑指 Offer II 003. 前 n 个数字二进制中 1 的个数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
JDK8中一个数的二进制1的个数为Integer.bitCount

解法一
思路：1、双层循环，外层循环0~n，内层循环算出1的个数（余2除2）

class Solution {
public int[] countBits(int n) {
int[] arr = new int[n+1];
int i = 0;
while(n>=i){
int cat = i;
int count = 0;
while(cat>0){
if(cat%2>0){
count++;
}
cat/=2;
}
arr[i]=count;
i++;
}
return arr;
}
}

时间复杂度：O(nlogn)；
空间复杂度：O(n)；
解法二：利用 Brian Kernighan算法，可以在一定程度上进一步提升计算速度。Brian Kernighan算法的原理是：对于任意整数 x，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。

class Solution {
public int[] countBits(int n) {
int[] arr = new int[n+1];
int i = 0;
while(n>=i){
int cat = i;
int count = 0;
while(cat>0){
cat = cat & (cat-1);
count++;
}
arr[i]=count;
i++;
}
return arr;
}
}

时间复杂度：O(nlogn)；
空间复杂度：O(n)；

解法三：
动态规划+最高有效位
对于正整数 x，如果可以知道最大的正整数 y，使得 y≤x且 y是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是0，此时称 y为 x 的「最高有效位」

当(i & (i - 1)) == 0时，说明i是2的幂次方，二进制第一位为1其余为0。
highBit是指i的最高有效位。
动态规划：bits[i] = bits[i - highBit] + 1;

class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
int highBit = 0;
for (int i = 1; i <= n; i++) {
if ((i & (i - 1)) == 0) {
highBit = i;
}
bits[i] = bits[i - highBit] + 1;
}
return bits;
}
}

时间复杂度：O(n)；
空间复杂度：O(n)；

解法四：
方法三中需要实时维护最高有效位，当遍历到的数是 222 的整数次幂时，需要更新最高有效位。如果再换一个思路，可以使用「最低有效位」计算「一比特数」。
bits[i] = bits[i >> 1] + (i & 1);
bits[i >> 1]为，bits[i]的一半的二进制个数，(i & 1)是指舍去的最低位是1还是0。

class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1);
}
return bits;
}
}

时间复杂度：O(n)；
空间复杂度：O(n)；

解法五：
定义正整数 x 的「最低设置位」为 x 的二进制表示中的最低的 1所在位。例如，10 的二进制表示是 1010(2)，其最低设置位为 2，对应的二进制表示是 10(2)。
令 y=x & (x−1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数，显然 0≤y<x，bits[x]=bits[y]+1。因此对任意正整数 x，都有 bits[x]=bits[x & (x−1)]+1

class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
}