[LeetCode]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. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
题目大意：
编写程序寻找第n个"超级丑陋数"
超级丑陋数是指只包含给定的k个质因子的正数。例如，给定长度为4的质数序列primes = [2, 7, 13, 19]，前12个超级丑陋数序列为：[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]
注意：
(1) 1 被认为是超级丑陋数，无论给定怎样的质数列表.
(2) 给定的质数列表以升序排列.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
解题思路：
解法I：
时间复杂度O(n * k)，k为primes的长度
参考Ugly Number II http://bookshadow.com/weblog/2015/08/19/leetcode-ugly-number-ii/
Java代码：
Read full article from [LeetCode]Super Ugly Number | 书影博客
No comments:
Post a Comment