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

发布时间：2020-12-14 05:06:34 所属栏目：百科来源：网络整理

导读：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

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.max
12             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] += 1
19                     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] += 1
17             }
18         }
19         
20         return res.last!
21     }
22 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!