[Swift]LeetCode386.字典序排数|LexicographicalNumbers

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10283535.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 的字典顺序。

例如，

给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

请尽可能的优化算法的时间复杂度和空间复杂度。输入的数据 n 小于等于 5,000,000。

112ms

 1 class Solution {
 2     func lexicalOrder(_ n: Int) -> [Int] {
 3         var res:[Int] = [Int]()
 4         for i in 1...9
 5         {
 6             helper(i, n, &res)
 7         }
 8         return res
 9     }
10     
11     func helper(_ cur:Int,_ n:Int,_ res:inout[Int])
12     {
13         if cur > n {return}
14         res.append(cur)
15         for i in 0...9
16         {
17             if cur * 10 + i <= n
18             {
19                 helper(cur * 10 + i, n, &res)
20             }
21             else
22             {
23                 break
24             }
25         }
26     }
27 }

152ms

 1 class Solution {
 2     func lexicalOrder(_ n: Int) -> [Int] {
 3         var res = [Int]()
 4         for i in 1 ... 9 {
 5             dfs(i, n, &res)
 6         }
 7         
 8         return res
 9     }
10     
11     func dfs(_ cur: Int, _ n: Int, _ res: inout [Int]) {
12         if cur > n {
13             return
14         }
15         res.append(cur)
16         for i in 0 ... 9 {
17             if cur * 10 + i > n {
18                 return
19             }
20             dfs(cur * 10 + i, n, &res)
21         }
22     }
23 }

184ms

 1 class Solution {
 2     func lexicalOrder(_ n: Int) -> [Int] {
 3         var result = [Int]()
 4         var current = 1
 5         for i in 1 ... n {
 6             result.append(current)
 7             if current * 10 <= n {
 8                 current = current * 10
 9             } else if current % 10 != 9 && current + 1 <= n {
10                 current += 1
11             } else {
12                 while (current / 10) % 10 == 9 {
13                     current = current / 10
14                 }
15                 current = current / 10 + 1
16             }
17         }
18         return result
19     }
20 }