LeetCode_DFS_中等_386.字典序排数

冷不防 2023-10-06 23:36 17阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

**给你一个整数 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/lexicographical-numbers

## 2.思路 ##

（1）字符串转换  
**如果不考虑时间复杂度和空间复杂度**，可以先将 \[1, n\] 内整数转换为对应的字符串并存储到数组 strNum 中，然后再对 strNum 中的元素进行排序，最后再将其结果保存到 res 中并返回即可。该方法时间复杂度和空间复杂度分别为 O(nlogn) 和 O(n)。

（2）深度优先搜索  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————字符串转换
    class Solution {
        
        public List<Integer> lexicalOrder(int n) {
        
            List<Integer> res = new ArrayList<>();
            //将 [1, n] 内整数转换为对应的字符串
            String[] strNum = new String[n];
            for (int i = 0; i < n; i++) {
        
                strNum[i] = String.valueOf(i + 1);
            }
            Arrays.sort(strNum);
            for (int i = 0; i < n; i++) {
        
                res.add(Integer.parseInt(strNum[i]));
            }
            return res;
        }
    }

//思路2————深度优先搜索
    class Solution {
        
        public List<Integer> lexicalOrder(int n) {
        
            List<Integer> res = new ArrayList<>();
            int num = 1;
            for (int i = 0; i < n; i++) {
        
                res.add(num);
                if (num * 10 <= n) {
        
                    num *= 10;
                } else {
        
                    while (num % 10 == 9 || num + 1 > n) {
        
                        num /= 10;
                    }
                    num++;
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/lexicographical-numbers/solution/zi-dian-xu-pai-shu-by-leetcode-solution-98mz/