[Swift]LeetCode313. 超级丑数 | Super Ugly Number

概述Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. Example: Input: n = 12, = Output: 32

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime List primes of size k.

Example:

input: n = 12,= Output: 32 Explanation: is the sequence of the first 12              super ugly numbers given  =  of size 4.primes[2,7,13,19][1,2,4,8,14,16,19,26,28,32]primes[2,19]

Note:

1 is a super ugly number for any given primes. The given numbers in primes are in ascending order. 0 < k ≤ 100,0 < n ≤ 106,0 < primes[i] < 1000. The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

编写一段程序来查找第 n 个超级丑数。

超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

示例:

输入: n = 12,= 输出: 32 解释: 给定长度为 4 的质数列表 primes = [2,19]，前 12 个超级丑数序列为：[1,32] 。primes[2,19]

说明:

1 是任何给定 primes 的超级丑数。  给定 primes 中的数字以升序排列。 0 < k ≤ 100,0 < primes[i] < 1000 。 第 n 个超级丑数确保在 32 位有符整数范围内。

116 ms

 1 class Solution { 2     func nthSuperUglyNumber(_ n: Int,_ primes: [Int]) -> Int { 3         let count = primes.count 4          5         var index = Array(repeatElement(0,count: count)) 6         var value = primes 7         var temp = 0 8  9         var ugly = [1]10         for _ in 0..<n - 1 {11             temp = Int.max12             for j in 0..<count {13                 temp = min(temp,value[j])14             }15             ugly.append(temp)16             for j in 0..<count {17                 if temp == value[j] {18                     index[j] += 119                     value[j] = ugly[index[j]] * primes[j]20                 }21             }22         }23         return ugly[n - 1]24     }25 }

556ms

 1 class Solution { 2     func nthSuperUglyNumber(_ n: Int,_ primes: [Int]) -> Int { 3         var res = [1]  4         var c = Array(repeating: 0,count: primes.count) 5          6         for _ in 0 ..< n-1 { 7             var comp = [Int]() 8             for i in 0 ..< primes.count { 9                 comp.append(res[c[i]] * primes[i])10             }11             12             let minP = comp.min()!13             res.append(minP)14             15             for j in 0 ..< comp.count where comp[j] == minP {16                 c[j] += 117             }18         }19         20         return res.last!21     }22 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode313. 超级丑数 | Super Ugly Number全部内容，希望文章能够帮你解决[Swift]LeetCode313. 超级丑数 | Super Ugly Number所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。