在数学，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法 。
386.字典序排数（LeetCode）
题目如下：
1
2
3
4
|
给定一个整数 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开始找出剩下的值。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
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));
}
}
}
|
结果如下：
时间复杂度为O(n)，空间复杂度为O(1)。
440.字典序的第k小数字
题目
1
2
|
给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。（**不是按照数字的标准，而是按照字典树的排序**）
注意：1 ≤ k ≤ n ≤ 109。
|
示例
1
2
3
4
5
6
|
输入:
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个单词。
1
|
输入描述：输入包括一行三个整数n,m,k(1<=n,m<=100),1<=k<=10^9)，以空格分割。
|
1
|
输出描述：输出第k个字典中的字符串，如果无解，输出-1
|
2.示例
说明
1
|
字典中的字符串依次为aazz azaz azza zaaz zaza zzaa
|