leetcode 313. Super Ugly Number 超级丑数

男娘i 2022-06-07 01:06 156阅读 0赞

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.  
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

这道题不太懂，还需要进一步思考。

建议和上一道题[leetcode 263. Ugly Number][] 、 [leetcode 264. Ugly Number II][]一起学习，

代码如下：

import java.util.Arrays;
    
    /*
     * http://www.cnblogs.com/grandyang/p/5144918.html
     * 
     * 由于我们不知道质数的个数，我们可以用一个idx数组来保存当前的位置，
     * 然后我们从每个子链中取出一个数，找出其中最小值，然后更新idx数组对应位置，
     * 注意有可能最小值不止一个，要更新所有最小值的位置.
     * */
    public class Solution 
    {
        public int nthSuperUglyNumber(int n, int[] primes)
        {
            int[] dp = new int[n];
            dp[0] = 1;
            int[] idxPrimes = new int[primes.length];
            int counter = 1;
            while (counter < n)
            {
                int min = Integer.MAX_VALUE;
                for (int i = 0; i < primes.length; i++) 
                {
                    // idxPrimes[i]代表每个丑数的个数，
                    // 比如丑数2题目的2，3，5，
                    // idxPrimes[0]代表2的下标
                    // idxPrimes[1]代表3的下标
                    // idxPrimes[2]代表5的下标
                    int temp = dp[idxPrimes[i]] * primes[i];
                    min = Math.min(min, temp);
                }
    
                // 如果min和 dp[idxPrimes[i]] * primes[i]相等，
                // 则其对应的下标++
                for (int i = 0; i < primes.length; i++) 
                {
                    if (min == dp[idxPrimes[i]] * primes[i]) 
                        idxPrimes[i]++;
                }
                dp[counter++] = min;
            }
            return dp[n - 1];
        }
    }

下面是C++的做法，就是一个简单的DP，我个人是不出来这种做法的，但是这个方法真的很棒

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int nthSuperUglyNumber(int n, vector<int>& primes) 
        {
            vector<int> dp(n, 0);
            dp[0] = 1;
            vector<int> index(primes.size(),0);
            int count = 1;
            while (count < n)
            {
                int minNum = numeric_limits<int>::max();
                for (int i = 0; i < primes.size(); i++)
                {
                    int tmp = dp[index[i]] * primes[i];
                    minNum = min(minNum, tmp);
                }
    
                for (int i = 0; i < primes.size(); i++)
                {
                    if (dp[index[i]] * primes[i] == minNum)
                        index[i]++;
                }
                dp[count++] = minNum;
            }
            return dp[n - 1];
        }
    
        int nthSuperUglyNumberBySet(int n, vector<int>& primes) 
        {
            vector<int> res;
            set<int> one{ 1 };
            while (res.size() < n)
            {
                int minNum = *(one.begin());
                one.erase(one.begin());
                for (int p : primes)
                    one.insert(minNum*p);
                res.push_back(minNum);
            }
            return res[n - 1];
        }
    };

[leetcode 263. Ugly Number]: http://blog.csdn.net/jackzhang_123/article/details/78109379
[leetcode 264. Ugly Number II]: http://blog.csdn.net/jackzhang_123/article/details/78109430