在數(shù)學，字典或詞典順序（也稱為詞匯順序，字典順序，字母順序或詞典順序）是基于字母順序排列的單詞按字母順序排列的方法 。

386.字典序排數(shù)（LeetCode）

題目如下：

給定一個整數(shù) n, 返回從 1 到 n 的字典順序。
例如，
給定 n =13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
請盡可能的優(yōu)化算法的時間復(fù)雜度和空間復(fù)雜度。 輸入的數(shù)據(jù) n 小于等于 5,000,000。

解題思路：

從輸入的1開始遍歷，分三種情況討論：

• 當n乘以10的時候小于N，就把10這個數(shù)加入list中；
• 然后此時的n已經(jīng)等于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));
        }
    }
}

結(jié)果如下：

image.png

時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。

440.字典序的第k小數(shù)字

題目

給定整數(shù) n 和 k，找到 1 到 n 中字典序第 k 小的數(shù)字。（**不是按照數(shù)字的標準，而是按照字典樹的排序**）
注意：1 ≤ k ≤ n ≤ 109。

示例

輸入:
n: 13   k: 2
輸出:
10
解釋:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的數(shù)字是 10。

從上面的代碼可知，list中存放的已經(jīng)是排序好的字典樹。直接list.get(k-1)就可以得出答案了。

1.題目描述

小易在學校中學習了關(guān)于字符串的理論，于是他基于此完成了一個字典的項目。小易的這個字典很奇特，字典內(nèi)的每個單詞都包含n個“a”和m個“z”，并且所有單詞按照字典序列。小易現(xiàn)在希望你能他找出第k個單詞。

輸入描述：輸入包括一行三個整數(shù)n,m,k(1<=n,m<=100),1<=k<=10^9)，以空格分割。

輸出描述：輸出第k個字典中的字符串，如果無解，輸出-1

2.示例

輸入：2 2 6

輸出：zzaa

說明

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