统计数字问题算法

末蓝、 2022-10-10 09:39 157阅读 0赞

**简述：就是你输入一个页数，查看从1到你输入的这一页，0到9个出现的次数。**

有两种算法：（根据需要而定）

（1）使用计数，即**：用一个for循环语句和一个while来统计这几个数出现的次数**

他使用简单，容易理解，但是效率太低，对于一个小整数而言，他是很好的一个算吗，但是对于一个100万以上的数，他的时间往往让人无法等待，百万的数就是几秒中。而千万级的数，就是几十秒甚至几分钟，，上亿时，他的时间就是3或4分钟。代码如下：

public static void tongji1()
    	{
    		int []tongji=new int[10];
    		Scanner scanner=new Scanner(System.in);
    		long yema=scanner.nextLong();
    		long j1=System.currentTimeMillis();
    		for(int i=1;i<=yema;i++)
    		{
    			int temp=i;
    			while(temp>0)
    			{
    				int n=temp%10;
    				tongji[n]++;
    				temp/=10;
    			}
    		}
    		long j2=System.currentTimeMillis();
    		System.out.println(j2-j1);
    			
    	}

（2）他不再同二重循环了，因为i她的时间复杂度太高了，（N方），而他的时间复杂度较低。

他不容易理解，但是效率高，代码长，他计算一个上亿的，就是不再是用毫秒单位计算了，往往使用微妙，上衣的就是几百围标，相当于0毫秒，

代码如下：

public static void tongji2()
    	{
    		int []tongji=new int[10];
    		Scanner scanner=new Scanner(System.in);
    		long yema=scanner.nextLong();
    		long j1=System.currentTimeMillis();
    		int len=0;//计算她的长度-1
    		long temp=yema;
    		//将设页码是从0开始，并且前面有多余的0,以你输入的为主：990：000-990
    		tongji[0]=-1;
    		while(temp>=10)
    		{
    			len++;
    			//减去多余的0
    			tongji[0]-=Math.pow(10, len);
    			temp/=10;
    		}
    		jsshu(tongji, len, yema);
    		long j2=System.currentTimeMillis();
    		System.out.println(j2-j1);
    		System.out.println(Arrays.toString(tongji));
    	}
    	
    	public static void jsshu(int []a,int len,long yema)
    	{
    		if(yema<10)
    		{
    			for(int i=0;i<=yema;i++)
    			{
    				a[i]++;
    			}
    			return;
    		}
    		else
    		{
    			//10的几次放
    			long zuida=(long) Math.pow(10, len);
    			//统计你输入的输的0-9基本变化量，公式：(len-1)*10^(len-2)
    			long bhl=(long) (len*zuida/10);
    			int max=(int) (yema/zuida);
    			long yushu=yema%zuida;
    			for(int i=0;i<max;i++)
    			{
    				a[i]+=zuida;
    			}
    			for(int i=0;i<10;i++)
    			{
    				a[i]+=max*bhl;
    			}
    			if(yushu==0)
    			{
    				a[0]+=len;
    				a[max]++;
    			}
    			else
    			{
    				int l=0;
    				//余数，有没有少加0；例如70001，余数1，他中间的令就没有价
    				while((zuida/=10)>yushu)
    				{
    					l++;
    				}
    				a[0]+=(l*(yushu+1));
    				a[max]+=(yushu+1);
    				jsshu(a, len-l-1, yushu);
    			}
    		}
    	}

有什么问题，提出来。能力有限。见谅