[Swift]LeetCode1201. 丑数 III | Ugly Number III

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

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

class Solution {
    func nthUglyNumber(_ n: Int, _ a: Int, _ b: Int, _ c: Int) -> Int {
        var low:Int = 0
        var high:Int = Int.max
        while (low < high)
        {
            let mid:Int = (low + high) / 2
            if countUgly(mid, a, b, c) < n
            {
                low = mid + 1
            }
            else
            {
                high = mid
            }
        }
        return low
    }
    
    //MARK:Stein算法
    func gcd(_ a:Int,_ b:Int) -> Int
    {
        var a = a
        var b = b
        var acc:Int = 0
        while((a & 1) == 0 && (b & 1) == 0)
        {
            acc += 1
            a >>= 1
            b >>= 1
        }
        while ((a & 1) == 0) {a >>= 1}
        while ((b & 1) == 0) {b >>= 1}
        if a < b {swap(&a,&b)}
        while (a != 0)
        {
            while ((a & 1) == 0)
            {
                a >>= 1
            }
            if a < b{swap(&a,&b)}
            a = (a - b) >> 1
        }
        return b << acc
    }
    
    func swap(_ x:inout Int,_ y:inout Int)
    {
        x = x ^ y
        y = x ^ y
        x = x ^ y
    }
    
    func lcm( _ x: Int, _ y: Int) -> Int
    {
        return x / gcd(x, y) * y
    }
    
    func countUgly(_ n: Int, _ a: Int, _ b: Int, _ c: Int) -> Int
    {
        var answer = n / a + n / b + n / c
        answer -= n / lcm(a, b) + n / lcm(b, c) + n / lcm(c, a)
        answer += n / lcm(lcm(a, b), c)
        return answer
    }
}

---

12ms

class Solution {
    var a = 0 
    var b = 0
    var c = 0 
    func nthUglyNumber(_ n: Int, _ a: Int, _ b: Int, _ c: Int) -> Int {
        var left = 2
        var right = Int.max
        self.a = a
        self.b = b
        self.c = c
    
        while left < right {
            let mid = left + (right - left) / 2
           
            if rank(mid) >= n {
                right = mid
            } else {
                left = mid + 1
            }
        }
        
        return left
    }
    
    fileprivate func rank(_ num: Int) -> Int {
    
        var result = 0
        result += num / a
        result += num / b
        result += num / c
        
        result += num / lcm(c, lcm(a, b))
        result -= num / lcm(a, b)
        result -= num / lcm(a, c)
        result -= num / lcm(c, b)
        return result
    }
    
    fileprivate func gcd(_ a:Int, _ b:Int) -> Int {
        if a == 0 { return b }
        return gcd(b % a, a)
    }

    fileprivate func lcm(_ a:Int, _ b:Int) -> Int {
        return (a * b) / gcd(a, b)
    }
}