[Swift]LeetCode264.丑数II|UglyNumberII

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

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

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

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

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

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

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1 is typically treated as an ugly number.
n does not exceed 1690.

编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1 是丑数。
n 不超过1690。

16ms

 1 class Solution {
 2     func nthUglyNumber(_ n: Int) -> Int {
 3         if n == 1 { return 1}
 4         var val1 = 2
 5         var val2 = 3
 6         var val3 = 5
 7         var i1 = 0
 8         var i2 = 0
 9         var i3 = 0
10         var result = [1]
11         for i in 1 ..< n {
12             let current = min(min(val1, val2), val3)
13             result.append(current)
14             if current == val1 {
15                 i1 += 1
16                 val1 = result[i1] * 2
17             }
18             if current == val2 {
19                 i2 += 1
20                 val2 = result[i2] * 3
21             }
22             if current == val3 {
23                 i3 += 1
24                 val3 = result[i3] * 5
25             }
26         }
27         return result[n - 1]
28     }
29 }

20ms

 1 class Solution {
 2     func nthUglyNumber(_ n: Int) -> Int{
 3 
 4         var res = [1]
 5         var i2 = 0, i3 = 0, i5 = 0
 6         while res.count < n {
 7             let m2 = res[i2]*2, m3 = res[i3]*3, m5 = res[i5]*5
 8             let mn = min(min(m2, m3), m5)
 9             if m2 == mn { i2 += 1 }
10             if m3 == mn { i3 += 1 }
11             if m5 == mn { i5 += 1 }
12             res.append(mn)
13         }
14         return res.last!
15     }
16 }

36ms

 1 class Solution {
 2     func nthUglyNumber(_ n: Int) -> Int {
 3         var res = [1]
 4         var i = 0
 5         var j = 0
 6         var k = 0
 7         
 8         while res.count < n {
 9             
10             res.append(res[i] * 2)
11             i += 1
12 
13             while res[j] * 3 < res[i] * 2 || res[k] * 5 < res[i] * 2 {
14                 if res[j] * 3 < res[i] * 2 && res[j] * 3 < res[k] * 5 {
15                     if res[j] % 2 != 0 {
16                         res.append(res[j] * 3)
17                     }
18                     j += 1
19                 }
20                 else {
21                     if res[k] % 2 != 0 && res[k] % 3 != 0 {
22                         res.append(res[k] * 5)
23                     }
24                     k += 1
25                 }
26             }
27             
28         }
29         
30         return res[n-1]
31     }
32 }

44ms

 1 class Solution {
 2     func nthUglyNumber(_ n: Int) -> Int {
 3         var res = [1]
 4         var c2 = 0, c3 = 0, c5 = 0
 5         var t2, t3, t5: Int
 6         var minp: Int
 7         
 8         for _ in 1 ..< n {
 9             t2 = res[c2] * 2
10             t3 = res[c3] * 3
11             t5 = res[c5] * 5
12             minp = min(t2, t3, t5)
13             if t2 == minp {
14                 c2 += 1
15             }
16             if t3 == minp {
17                 c3 += 1
18             }
19             if t5 == minp {
20                 c5 += 1
21             }
22             res.append(minp)
23         }
24 
25         return res.last!
26     }
27 }