E2-C-1~n中每个数的二进制中1的个数

题目

输入 一个数n，表示本次对局换枪次数

输出 一行n个整数，表示1~n转化为二进制后数目1的个数

输入样例 5 输出样例 1 1 2 1 2 数据范围 1≤n≤107 Tips 遍历时计算二进制的复杂度为O(n*sizeof(int))

要求时间复杂度为O(n)

思路分析

题目中说要求时间复杂度为O(n)。 如果从1到n遍历，每一个数都求出二进制再计算1的个数肯定不行。 由于此处我们的数据是公差为1的等差数列，我们可以模拟二进制加一的过程。 即想求i二进制中1的个数，从低位至高位遍历i-1的二进制序列，如果本来某位置为1，加一进位，此处变为0，count–。如果本来某位置为0，直接加一，count++，此时序列已变成i的二进制序列，退出循环即可。

AC代码

#include<stdio.h> int store[10000010]={0}; int main() { int n,i,j,count=0; scanf("%d",&n); for(i=1;i<=n;i++) { j=0; while(1) { if(store[j]==0) { store[j]=1; count++; break; } if(store[j]==1) { store[j]=0; count--; } j++; } printf("%d ",count); } }