求1~n中0~9出现的次数

- 日理万妓 2022-06-07 01:56 136阅读 0赞

> 题目来至牛客网：[页码统计][Link 1]  
> 牛牛新买了一本算法书，算法书一共有n页，页码从1到n。牛牛于是想了一个算法题目：在这本算法书页码中0~9每个数字分别出现了多少次？  
> 输入描述:
> 
> 输入包括一个整数n(1 ≤ n ≤ 1,000,000,000)
> 
> 输出描述:
> 
> 输出包括一行10个整数，即0~9这些数字在页码中出现的次数，以空格分隔。行末无空格。  
> 示例1  
> 输入
> 
> 999  
> 输出
> 
> 189 300 300 300 300 300 300 300 300 300

解法一

##### 暴力破解 #####

public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner cin = new Scanner(System.in);
            int n = cin.nextInt();
    
            int res[] = new int[10];
    
            for (int i = 1; i <=n; i++) {
                count(res, i);
            }
    
            for (int i = 0; i < 10; i++) {
                if (i != 0) {
                    System.out.print(" ");
                }
                System.out.print(res[i]);
            }
    
        }
    
    //依次每一位求解：因为一个数i的时间复杂度为log(n),有n个数，所以总体时间复杂度是：nlog(n)。
    public static void count(int res[], int n) {
            //虽然简单明了，但是复杂度太高
            while (n != 0) {
                res[n % 10]++;
                n /= 10;
            }
    
        }

解法二

##### 数字规律 #####

拿123举例，假设需要求1出现的个数，我们可以计算每一位上出现的个数。假设1出现在个位时数的格式是XX1 ，前面的XX能组成的个数就是1在个位时出现的次数。XX可以组成00~12共13个数。所以1在个位出现13次。当1在十位时，X1X，则可以组成（0~1）\*（0~9）种，为什么是0~9呢？因为十位为1时能组成的最大数是119，小于123所以个位可以是0~9。如果我们是求2的次数的话就需要另外判断了，因为格式为12X能组成的数最大是123，不能是124~129，所以，只需要判断一下当前位的数和需要求出现次数的数之间的关系即可。  
代码如下：

/**
    **  num：代表题目中的n ，target：需要统计的数
    **/
    public static int getCount(int num, int target) {
            //表示当前的位数（个位、十位。。。）
            int base = 1;
            //结果
            int sum = 0;
            int n = num;
    
            while (n != 0) {
                //以123为例，当1在个位时sum+= 1*12,并没有加13是因为我们还没有判断当前位的数cur跟要求的数的关系。
                sum += base * (n / 10);
                //cur当前位的数如123中个位的数是3
                int cur = n % 10;
    
                if (cur == target) {
                //当cur等于target,比如123，处于十位时求2出现的次数，因为只能有120~123四种情况所以，对应sum += num % base + 1
                    sum += num % base + 1;
                } else if (cur > target) {
                    //当cur大于target,比如123，处于个位时求1出现的次数，需要加上12开头的情况，所以sum += 1 * base。
                    sum += 1 * base;
                }else if(cur<target){
                    //当cur小于target,比如123，处于个位时求5出现的次数，这是125是不成立的。
                }
    
                base *= 10;
                n = n / 10;
            }
    
            return sum;
    
        }

上述代码只能处理1~9的情况，当求0出现的次数时需要额外考虑，比如00X和0X0以及0XX都是0，这显然不在题目的考虑范围之类，所以，只需要将这种情况去掉即可：  
代码如下：

public static int getCount0(int num) {
    
            int base = 1;
            int sum = 0;
            int n = num;
    
            while (n != 0) {
                //区别在于这一行代码，减掉了1
                sum += base * (n / 10 - 1);
    
                int cur = n % 10;
                if (cur == 0) {
                    sum += num % base + 1;
                } else if (cur > 0) {
                    sum += base;
                }
    
                base *= 10;
                n = n / 10;
            }
    
            return sum;
    
        }

所以，牛客课网题目的答案如下：

import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
    
            Scanner cin = new Scanner(System.in);
            int n = cin.nextInt();
    
            int res[] = new int[10];
    
            res[0] = getCount0(n);
            for (int i = 1; i < 10; i++) {
                res[i] = getCount(n, i);
            }
    
            for (int i = 0; i < 10; i++) {
                if(i!=0){
                    System.out.print(" ");
                }
                System.out.print(res[i]);
            }
    
        }
    
        public static int getCount(int num, int target) {
    
            int base = 1;
            int sum = 0;
            int n = num;
    
            while (n != 0) {
    
                sum += base * (n / 10);
    
                int cur = n % 10;
                if (cur == target) {
                    sum += num % base + 1;
                } else if (cur > target) {
                    sum += base;
                }
    
                base *= 10;
                n = n / 10;
            }
    
            return sum;
    
        }
    
        public static int getCount0(int num) {
    
            int base = 1;
            int sum = 0;
            int n = num;
    
            while (n != 0) {
    
                sum += base * (n / 10 -1);
    
                int cur = n % 10;
                if (cur == 0) {
                    sum += num % base + 1;
                } 
                else if (cur > 0) {
                    sum += base;
                }
    
                base *= 10;
                n = n / 10;
            }
    
            return sum;
    
        }
    }

当然，也可以参考这篇博客：[经典的数1问题][1]

[Link 1]: https://www.nowcoder.com/questionTerminal/3a003cb6a3174ef9835fa603e01d8b52
[1]: http://blog.csdn.net/sallyxyl1993/article/details/60882064