字典序

1. import java.util.Scanner;

2. public class Main {

3.     //包括自己的节点数，即字典树的数字pre分支的所有节点数

4.     //pre分支的深度为1的孩子:pre*10,pre*10+1,pre*10+2,...,pre*10+10-1,孩子数为10

5.     //pre分支的深度为2的孩子:pre*100,pre*100+1,pre*100+2,...,pre*100+100-1,孩子数为100

6.     private static long getAllChildCount(long pre,long n){

7.         long count=1;//计算自己的节点数

8.         //pre*10是pre深度为1的第一个孩子的数字,pre*100是pre深度为2的第一个孩子的数字

9.         //pre*p<=n,即检测在第某个深度下，是否存在该深度的第一孩子，若该孩子不存在，在该深度下，肯定不会有其他孩子存在。若存在循环累加计算

10.         //pre*p+p-1,即pre的某个深度下，最右边的孩子的数字（不考虑n情况）

11.         for(long p=10;pre*p<=n;p*=10){

12.             if(pre*p+p-1<=n) count+=p;

13.             else count+=(n-pre*p+1);//这里+1是因为[1,n],n也要算进去

14.         }

15.         return count;

16.     }

18.     //该函数是寻找第m个数是什么，通过节点数进行分支选择

19.     //如果该分支的节点数较m来说过少，那么第m的数肯定不在这个分支上，检测下个分支

20.     //检测下个分支的时候，不是在这个分支寻找第m的数字，而是寻找第（m-上一个分支的节点数）的数

21.     //如果分支的节点数较m来说过多， 选择该分支，如果m为1，那么答案就是这个分支的根节点

22.     private static long find(long n,long m){

23.         long ans=1;//默认在第1分支寻找

24.         while(m!=0){

25.             long v=getAllChildCount(ans, n);//获得该分支的节点数

26.             if(v<m) {

27.                 m-=v;

28.                 ans++;//检测下一个分支

29.                 continue;

30.             }

31.             //找到了

32.             if(m==1) break;

33.             //在该分支的孩子分支上,从第一孩子开始寻找

34.             ans*=10;

35.             m--;//是在孩子分支的第m-1个上

36.         }

37.         return ans;

38.     }

39.     //注意是long

40.     public static void main(String[] argv){

41.         Scanner input=new Scanner(System.in);

42.         long n=input.nextLong();

43.         long m=input.nextLong();

44.         System.out.println(find(n,m));    

45.     }

46. }

    
    

import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int[] array=new int[n];
String[] str=new String[n];
for(int i=0;i<n;i++) {
array[i]=i+1;
str[i]=Integer.toString(array[i]);
}
Arrays.sort(str);
//compareNum(array);
System.out.println(str[m-1]);
}

}
直接用字符串的比较排序即可，复杂度很低，不知道为啥运算超时

学习别人的代码：和递归树类似，字典序也可以看成树形结构（逻辑上），分别从两个角度寻找第m个数（子节点，兄弟节点）。

import java.util.*;

public class Main {
    long getCountByPrifx(long currentPrifxCount,long n){
        long count = 1;
        long p = 10;
        for(;currentPrifxCount * p <= n; p *= 10){
            if (currentPrifxCount * p - 1 + p < n) {
                count += p;
            }else {
                count += n - currentPrifxCount * p + 1;
            }
        }
        return count;
    }

    long getNumFromDict(long n,long mth){
        long ans = 1;
        long count ;
        while (mth != 0){
            //当前节点开头的数字个数
            count = getCountByPrifx(ans,n);
            if (count >= mth){
                //count >= mth && mth != 0 的含义是当前节点不是要找的点，也不在兄弟k开头的数字中，向子节点开头的数字遍历
                mth--;
                if (mth == 0) break;
                //以当前 0号子节点为前者继续找
                ans *= 10;

            }else {
                //兄弟节点中找
                mth -= count;
                ans++;
            }
        }
        return ans;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            long n = sc.nextLong();
            long m = sc.nextLong();
            System.out.println(new Main().getNumFromDict(n,m));
        }
        sc.close();
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            long n =sc.nextLong();
            long m =sc.nextLong();

            long i = 1;//从1开始数
            m--;
            while(m!=0){
                long num = 0;
                long start = i,end = i+1;
                while(start<=n){
                    num += Math.min(n+1,end)-start;
                    start*=10;
                    end*=10;
                }
                if(num>m){
                    i *= 10;
                    m--;
                }else{
                    m-=num;
                    i++;
                }

            }

            System.out.println(i);



        }

    }



}