p386

发表于 | 分类于 |

LeetCode p386 Lexicographical Numbers 题解

1.题目：

Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

题意：

给一个数n,返回1-n的字典序排列。

2.解题思路:

见代码，注意0的出现。如1-100 1 10 100 101…..109 11 110

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
public class Solution {
    public List<Integer> lexicalOrder(int n) {
       List<Integer> ans = new ArrayList<>(n);
		if (n < 1)
			return ans;
		ans.add(1);
		int c = 1;
		for (int i = 1; i < n; i++) {
			if (c * 10 <= n) {
				c = c * 10;
			} else {
				while (c % 10 == 9 || c == n) { //出现9回退
					c = c / 10;
				}
				c++;
			}
			ans.add(c);
		}

		return ans;
    }
}

4.一些总结：