求1~n中0~9出现的次数-蒲公英云

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

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

题目来至牛客网：页码统计
牛牛新买了一本算法书，算法书一共有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;
    }
}