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
- class Solution {
- func nthUglyNumber(_ n: Int) -> Int {
- if n == 1 { return 1}
- var val1 = 2
- var val2 = 3
- var val3 = 5
- var i1 = 0
- var i2 = 0
- var i3 = 0
- var result = [1]
- for i in 1 ..<n {
- let current = min(min(val1, val2), val3)
- result.append(current)
- if current == val1 {
- i1 += 1
- val1 = result[i1] * 2
- }
- if current == val2 {
- i2 += 1
- val2 = result[i2] * 3
- }
- if current == val3 {
- i3 += 1
- val3 = result[i3] * 5
- }
- }
- return result[n - 1]
- }
- }
- 20ms
- class Solution {
- func nthUglyNumber(_ n: Int) -> Int{
- var res = [1]
- var i2 = 0, i3 = 0, i5 = 0
- while res.count <n {
- let m2 = res[i2]*2, m3 = res[i3]*3, m5 = res[i5]*5
- let mn = min(min(m2, m3), m5)
- if m2 == mn { i2 += 1 }
- if m3 == mn { i3 += 1 }
- if m5 == mn { i5 += 1 }
- res.append(mn)
- }
- return res.last!
- }
- }
- 36ms
- class Solution {
- func nthUglyNumber(_ n: Int) -> Int {
- var res = [1]
- var i = 0
- var j = 0
- var k = 0
- while res.count <n {
- res.append(res[i] * 2)
- i += 1
- while res[j] * 3 < res[i] * 2 || res[k] * 5 < res[i] * 2 {
- if res[j] * 3 < res[i] * 2 && res[j] * 3 < res[k] * 5 {
- if res[j] % 2 != 0 {
- res.append(res[j] * 3)
- }
- j += 1
- }
- else {
- if res[k] % 2 != 0 && res[k] % 3 != 0 {
- res.append(res[k] * 5)
- }
- k += 1
- }
- }
- }
- return res[n-1]
- }
- }
- 44ms
- class Solution {
- func nthUglyNumber(_ n: Int) -> Int {
- var res = [1]
- var c2 = 0, c3 = 0, c5 = 0
- var t2, t3, t5: Int
- var minp: Int
- for _ in 1 ..< n {
- t2 = res[c2] * 2
- t3 = res[c3] * 3
- t5 = res[c5] * 5
- minp = min(t2, t3, t5)
- if t2 == minp {
- c2 += 1
- }
- if t3 == minp {
- c3 += 1
- }
- if t5 == minp {
- c5 += 1
- }
- res.append(minp)
- }
- return res.last!
- }
- }
[Swift]LeetCode264. 丑数 II | Ugly Number II
来源: http://www.bubuko.com/infodetail-2911126.html