313. 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, primes = [2, 7, 13, 19]
Output: 32 
Explanation: [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 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.

Approach #1: C++.

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        unordered_map<int, int> mp;
        vector<int> nums;
        nums.push_back(1);
        while (nums.size() != n) {
            int temp = INT_MAX;
            for (int i = 0; i < primes.size(); ++i) {
                temp = min(temp, nums[mp[primes[i]]] * primes[i]);
            }
            for (int i = 0; i < primes.size(); ++i) {
                if (temp == nums[mp[primes[i]]]*primes[i]) 
                    mp[primes[i]]++;
            }
            nums.push_back(temp);
        }
        return nums[nums.size()-1];
    }
};

Approach #2: Java.

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
        int[] idx = new int[primes.length];
        
        ugly[0] = 1;
        for (int i = 1; i < n; ++i) {
            ugly[i] = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; ++j) {
                ugly[i] = Math.min(ugly[i], primes[j] * ugly[idx[j]]);
            }
            
            for (int j = 0; j < primes.length; ++j) {
                while (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;
            }
        }
        
        return ugly[n-1];
    }
}

Approach #3: Python.

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        ugly = [1] * n
        i_list = [-1] * len(primes)
        v_list = [1] * len(primes)
        k = 0
        while k < n:
            x = min(v_list)
            ugly[k] = x
            for v in xrange(len(i_list)):
                if x == v_list[v]:
                    i_list[v] += 1
                    v_list[v] = ugly[i_list[v]] * primes[v]
            k += 1
            
        return ugly[k-1]

相关推荐