题目

[386. Lexicographical Numbers](http:// https://leetcode.com/problems/lexicographical-numbers/)

题解

题目意思是给你一个N 实际是一串（1—N）的数字，然后让这个串安装字典序排序输出
实际上这道题的方法有很多就是看最后的运行时间和空间优化
1.第一种方法 直接生成 1到n的字符串列表 然后 用列表的sort排序最后转换为int列表就完事了
2.第二种方法. 直接推出已经排好的字典序列表

代码

第一种

   
fun lexicalOrder(n: Int): List<Int> {

       var list2: ArrayList<String> = arrayListOf()
    for (i in 1..n) {
        list2.add(i.toString())
    }
    list2.sort()
    var list = list2.map { it.toInt() }.toList()
    return list
}

第二种方法

fun lexicalOrder(n: Int): List<Int> {

    var list: ArrayList<Int> = arrayListOf()

    for (i in 1..9) {
        if (i <= n)
            list.add(i)
        var num = i  //前置基础数
        var fnum = 10 // 当前阶数
        setD(num * 10, list, n)
    }
    for (i in list.indices) {
        print("," + list[i])
    }
    return list
}

fun setD(num: Int, list: ArrayList<Int>, n: Int) {
    for (i in 0 until 10) {
        if (num + i <= n) {
            list.add(num + i)
            if ((num + i) * 10 <= n) {
                setD((num + i) * 10, list, n)
            }
        } else {
            return
        }
    }
}

第三种

是看评论里有一个c++说是时间最快 然后 按他思路写了kotlin的 发现并没有多快。。。
思路实际和我第二种方法一样就是推导出当前位置应该放哪个数字

  fun lexicalOrder(n: Int): List<Int> {
    var list: ArrayList<Int> = arrayListOf()
    var cur = 1
    for (i in 1..n) {
        list.add(cur)
        if (cur * 10 <= n) {
            cur *= 10
        } else {
            if (cur >= n)
                cur /= 10
            cur += 1
            while (cur % 10 == 0)
                cur /= 10

        }
    }
    for (i in list.indices) {
        print("," + list[i])
    }
    return list
}

提交结果

LeetCode 386. Lexicographical Numbers