leetcode Super Ugly Number

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.

题目地址: leetcode Super Ugly Number

题意：

给定因子Primes , 让你求第n个super ugly number。

super ugly number定义为：整数，且因子全部都在primes中。 注意1为特殊的super ugly number。

思路：

和 leetcode Ugly Number  II 思路一样，要使得super ugly number 不漏掉，那么用每个因子去乘第一个，当前因子乘积是最小后，乘以下一个.....以此类推。

C++

struct Node {
	int i;
	int val;
	int prime;
	Node(int i, int val, int prime) :i(i), val(val), prime(prime) {}
	bool operator < (const Node & b) const {
		return val > b.val;
	}
};

class Solution {
public:
	int nthSuperUglyNumber(int n, vector<int>& primes) {
		priority_queue<Node> q;
		for (int prime : primes) q.push(Node(0, prime, prime));
		vector<int> ans(n, 1);
		for (int i = 1; i < n; i++) {
			Node cur = q.top(); q.pop();
			ans[i] = cur.val;
			while (!q.empty() && q.top().val == cur.val) {
				Node t = q.top(); q.pop();
				t.val = ans[++t.i] * t.prime;
				q.push(t);
			}
			cur.val = ans[++cur.i] * cur.prime;
			q.push(cur);
		}
		return ans[n - 1];
	}
};

Java

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ans = new int[n];
        ans[0] = 1;
        PriorityQueue<Node> q = new PriorityQueue<Node>();
        for (int prime : primes) q.add(new Node(0, prime, prime));
        for (int i = 1; i < n; i++) {
            Node cur = q.poll();
            ans[i] = cur.val;
            while (!q.isEmpty() && q.peek().val == cur.val) {
                Node t = q.poll();
                t.val = ans[++t.i] * t.prime;
                q.add(t);
            }
            cur.val = ans[++cur.i] * cur.prime;
            q.add(cur);
        }
        return ans[n - 1];
    }
}

class Node implements Comparable<Node> {
    int i;
    int val;
    final int prime;

    public Node(int i, int val, int prime) {
        this.i = i;
        this.val = val;
        this.prime = prime;
    }

    @Override
    public int compareTo(Node o) {
        return this.val - o.val;
    }
}

Python

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        ans = [1] * n
        q = [[prime, 0, prime] for prime in primes]
        heapq.heapify(q)
        for i in range(1, n):
            cur = heapq.heappop(q)
            ans[i] = cur[0]
            while q and q[0][0] == ans[i]:
                t = heapq.heappop(q)
                t[1] += 1
                t[0] = ans[t[1]] * t[2]
                heapq.heappush(q, t)
            cur[1] += 1
            cur[0] = ans[cur[1]] * cur[2]
            heapq.heappush(q, cur)
        return ans[n - 1]