原文链接: https://leetcode-cn.com/problems/lexicographical-numbers

英文原文

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space. 

 

Example 1:

Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2:

Input: n = 2
Output: [1,2]

 

Constraints:

• 1 <= n <= 5 * 104

中文题目

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

 

示例 1：

输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

示例 2：

输入：n = 2
输出：[1,2]

 

提示：

• 1 <= n <= 5 * 104

通过代码

高赞题解

山谷里有座千年古刹，一日，方丈收到一个任务，将1-n的字典排序进行输出；
思绪良久，方丈找来9个大法师，对第一个大法师说：“大弟子，我现在给你一个任务，我给你一个数字1，你负责把这个数字开头的，并且不大于n的所有数字按照字典排序交付于我。”
接着又对第二个大法师说：“二弟子，我也给你一个任务，我给你一个数字2，你负责把这个数字开头的，并且不大于n的所有数字按照字典排序交付于我。”
如是依次对剩下弟子说了一遍，各大法师领命依次离去；
大法师归于禅室，思虑良久：方觉方丈之策可复行之，乃唤来座下大弟子十人，依次要求将10,11,12…19开头的并且不大于n的所有数字交付于己。众大弟子离去，效法以行。

public static List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>();
        lexicalOrder(result,null,n);
        return result;
    }

    public static void lexicalOrder(List<Integer> result,Integer currentValue,int maxNum) {
        if(currentValue != null && currentValue > maxNum){
            return;
        }
        if(currentValue != null) {
            result.add(currentValue);
        }
        for(int nextBit = 0; nextBit <= 9;nextBit++){
            if(currentValue == null ){
                if(nextBit == 0) {
                    continue;
                } else {
                    currentValue = 0;
                }
            }
            lexicalOrder(result,currentValue*10+nextBit,maxNum);
        }
    }

统计信息

通过次数	提交次数	AC比率
23893	31851	75.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言