题目描述：

Write a program to find the n^th 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 ≤ 10⁶, 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 ≤ 10⁶, 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代码：

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int size = primes.length;
        int q[] = new int[n];
        int idxes[] = new int[size];
        int vals[] = new int[size];
        q[0] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < size; j++) {
                vals[j] = q[idxes[j]] * primes[j];
            }
            q[i] = findMin(vals);
            for (int j = 0; j < size; j++) {
                if (vals[j] == q[i]) {
                    idxes[j] += 1;
                }
            }
        }
        return q[n - 1];
    }

    public int findMin(int[] nums) {
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            min = Math.min(min, nums[i]);
        }
        return min;
    }

}

解法II：

小顶堆（优先队列）

使用Python生成器和heapq.merge，将primes中各个元素的质数倍数合并在一起

参考StefanPochmann的答案：https://leetcode.com/discuss/72763/python-generators-on-a-heap

顺便可以学习一下heapq, itertools, yield的用法。

Python代码：

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        uglies = [1]
        def gen(prime):
            for ugly in uglies:
                yield ugly * prime
        merged = heapq.merge(*map(gen, primes))
        while len(uglies) < n:
            ugly = next(merged)
            if ugly != uglies[-1]:
                uglies.append(ugly)
        return uglies[-1]

Python代码（4行版本）：

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        uglies = [1]
        merged = heapq.merge(*map(lambda p: (u*p for u in uglies), primes))
        uniqed = (u for u, _ in itertools.groupby(merged))
        map(uglies.append, itertools.islice(uniqed, n-1))
        return uglies[-1]

 

本文链接：http://bookshadow.com/weblog/2015/12/03/leetcode-super-ugly-number/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码