Swift.丑数

题目描述：把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

import Foundation

class For34Solution {
    func kUglyNum(_ k: Int) -> Int {
        
        if k <= 0 {
            return 0
        }
        
        var uglyNums = [Int]()
        
        uglyNums.append(1)
        var ugly2 = 0
        var ugly3 = 0
        var ugly5 = 0
        var current = 1
        
        
        while current < k {
            
            let minUgly = min(uglyNums[ugly2]*2, uglyNums[ugly3]*3, uglyNums[ugly5]*5)
            uglyNums.append(minUgly)
            
            while uglyNums[ugly2]*2 <= minUgly {
                ugly2 += 1
            }
            while uglyNums[ugly3]*3 <= minUgly {
                ugly3 += 1
            }
            while uglyNums[ugly5]*5 <= minUgly {
                ugly5 += 1
            }
            
            current += 1
        }
        
        return uglyNums[current - 1]
    }
    
    
    func isUgly(_ n: Int) -> Bool {
        if n == 0 {
            return false
        }
        
        var num = n
        
        while num%2 == 0 {
            num /= 2
        }
        
        while num%3 == 0 {
            num /= 3
        }
        
        while num%5 == 0 {
            num /= 5
        }
        
        return num == 1
    }
}

算法思想：最简单的方法就是先通过将一个数不断除以2，3，5来判定该数是不是丑数，而后在从1开始，依次往后判断每个数是不是丑数，并记下丑数的个数，这样当计算的个数为给定值时，便是需要求的第n个丑数，这种方法的时间复杂度为O（k），这里的k为第n个丑数的大小，比如第1500个丑数的大小为859963392，那么就需要判断859963392次，时间效率非常低。
    直观的优化措施就是看能不能将时间复杂度降低到O（n），即只在丑数上花时间，而不在非丑数上浪费时间。剑指offer上给的思路很好，用O（n）的辅助空间来得到O(n)的时间复杂度。其核心思想是：每一个丑数必然是由之前的某个丑数与2，3或5的乘积得到的，这样下一个丑数就用之前的丑数分别乘以2，3，5，找出这三这种最小的并且大于当前最大丑数的值，即为下一个要求的丑数。

github地址：https://github.com/cubegao/LeetCode