[Swift]LeetCode1201.丑数III|UglyNumberIII

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

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

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

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

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

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

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

Ugly numbers are positive integers which are divisible by a or b or c.

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 12... The 4th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

Example 4:

Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984

Constraints:

1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
It's guaranteed that the result will be in range [1, 2 * 10^9]

请你帮忙设计一个程序，用来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的正整数。

示例 1：

输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。

示例 2：

输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。

示例 3：

输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。

示例 4：

输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
输出：1999999984

提示：

1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
本题结果在 [1, 2 * 10^9] 的范围内

Runtime: 12 ms

Memory Usage: 20.7 MB

 1 class Solution {
 2     func nthUglyNumber(_ n: Int, _ a: Int, _ b: Int, _ c: Int) -> Int {
 3         var low:Int = 0
 4         var high:Int = Int.max
 5         while (low < high)
 6         {
 7             let mid:Int = (low + high) / 2
 8             if countUgly(mid, a, b, c) < n
 9             {
10                 low = mid + 1
11             }
12             else
13             {
14                 high = mid
15             }
16         }
17         return low
18     }
19     
20     //MARK:Stein算法
21     func gcd(_ a:Int,_ b:Int) -> Int
22     {
23         var a = a
24         var b = b
25         var acc:Int = 0
26         while((a & 1) == 0 && (b & 1) == 0)
27         {
28             acc += 1
29             a >>= 1
30             b >>= 1
31         }
32         while ((a & 1) == 0) {a >>= 1}
33         while ((b & 1) == 0) {b >>= 1}
34         if a < b {swap(&a,&b)}
35         while (a != 0)
36         {
37             while ((a & 1) == 0)
38             {
39                 a >>= 1
40             }
41             if a < b{swap(&a,&b)}
42             a = (a - b) >> 1
43         }
44         return b << acc
45     }
46     
47     func swap(_ x:inout Int,_ y:inout Int)
48     {
49         x = x ^ y
50         y = x ^ y
51         x = x ^ y
52     }
53     
54     func lcm( _ x: Int, _ y: Int) -> Int
55     {
56         return x / gcd(x, y) * y
57     }
58     
59     func countUgly(_ n: Int, _ a: Int, _ b: Int, _ c: Int) -> Int
60     {
61         var answer = n / a + n / b + n / c
62         answer -= n / lcm(a, b) + n / lcm(b, c) + n / lcm(c, a)
63         answer += n / lcm(lcm(a, b), c)
64         return answer
65     }
66 }

12ms

 1 class Solution {
 2     var a = 0 
 3     var b = 0
 4     var c = 0 
 5     func nthUglyNumber(_ n: Int, _ a: Int, _ b: Int, _ c: Int) -> Int {
 6         var left = 2
 7         var right = Int.max
 8         self.a = a
 9         self.b = b
10         self.c = c
11     
12         while left < right {
13             let mid = left + (right - left) / 2
14            
15             if rank(mid) >= n {
16                 right = mid
17             } else {
18                 left = mid + 1
19             }
20         }
21         
22         return left
23     }
24     
25     fileprivate func rank(_ num: Int) -> Int {
26     
27         var result = 0
28         result += num / a
29         result += num / b
30         result += num / c
31         
32         result += num / lcm(c, lcm(a, b))
33         result -= num / lcm(a, b)
34         result -= num / lcm(a, c)
35         result -= num / lcm(c, b)
36         return result
37     }
38     
39     fileprivate func gcd(_ a:Int, _ b:Int) -> Int {
40         if a == 0 { return b }
41         return gcd(b % a, a)
42     }
43 
44     fileprivate func lcm(_ a:Int, _ b:Int) -> Int {
45         return (a * b) / gcd(a, b)
46     }
47 }