在线时间:8:00-16:00
迪恩网络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 }
|
请发表评论