• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode264.丑数II|UglyNumberII

原作者: [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. 1 is typically treated as an ugly number.
  2. n does not exceed 1690.

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

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

示例:

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

说明:  

  1. 1 是丑数。
  2. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift-初探webView与JS交互发布时间:2022-07-13
下一篇:
[Swift]LeetCode1175.质数排列|PrimeArrangements发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap