字典排序算法

在数学，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法 。

386.字典序排数（LeetCode）

题目如下：

给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

解题思路：

从输入的1开始遍历，分三种情况讨论：

• 当n乘以10的时候小于N，就把10这个数加入list中；
• 然后此时的n已经等于10了，再去判断11、12、13，通过n+1小于N来获得11、12、13；
• 最后，此时的n等于13，通过（n/10）%10等到1，在加上1。从2开始找出剩下的值。

代码如下：

package com.zhoujian.solutions.leetcode;
import java.util.ArrayList;
import java.util.List;

/**
 * @author zhoujian123@hotmail.com 2018/8/12 11:24
 */
public class DicOrder {
    public static List<Integer> lexicalOrder(int n){
        ArrayList<Integer> list = new ArrayList<Integer>();
        int curr = 1;
        for (int i = 1; i <=n ; i++) {
            list.add(curr);
            if (curr*10 <=n) {
                curr*=10;
            }else if (curr%10!=9&&curr+1<=n){
                curr++;
            }else {
                while ((curr/10)%10 ==9){
                    curr/=10;
                }
                curr = curr/10+1;
            }
        }

        return list;
    }
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<Integer>();
        arrayList = lexicalOrder(13);
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.println(arrayList.get(i));
        }
    }
}

结果如下：

image.png

时间复杂度为O(n)，空间复杂度为O(1)。

440.字典序的第k小数字

题目

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。（**不是按照数字的标准，而是按照字典树的排序**）
注意：1 ≤ k ≤ n ≤ 109。

示例

输入:
n: 13   k: 2
输出:
10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

从上面的代码可知，list中存放的已经是排序好的字典树。直接list.get(k-1)就可以得出答案了。

1.题目描述

小易在学校中学习了关于字符串的理论，于是他基于此完成了一个字典的项目。小易的这个字典很奇特，字典内的每个单词都包含n个“a”和m个“z”，并且所有单词按照字典序列。小易现在希望你能他找出第k个单词。

输入描述：输入包括一行三个整数n,m,k(1<=n,m<=100),1<=k<=10^9)，以空格分割。

输出描述：输出第k个字典中的字符串，如果无解，输出-1

2.示例

输入：2 2 6

输出：zzaa

说明

字典中的字符串依次为aazz azaz azza zaaz zaza zzaa