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 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.

二. 題目分析

題目的大意是，編寫程序尋找第n個“超級丑陋數“，以下給出超級丑數的定義：

超級丑數是指只包含給定的k個質因子的正數。例如，給定長度為4的質數序列primes = [2, 7, 13, 19]，前12個超級丑陋數序列為：[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]

注意：

1被認為是超級丑數，無論給定怎樣的質數列表。 給定的質數列表以升序排列。 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000。

一種方法是使用一個數組用於記錄每個primes內質數乘積的次數，用另一個數組存儲解第1到k個丑數的值。

三. 示例代碼

class Solution {  
public:  
    int nthSuperUglyNumber(int n, vector& primes) {  
        int len = primes.size();  
        vector index(len, 0);
        vector uglyNum(n, INT_MAX);
        vector temp(len);
        uglyNum[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            int minj = -1;
            int minNum = INT_MAX;

            for (int j = 0; j < len; ++j)
            {
                temp[j] = primes[j] * uglyNum[index[j]];
                if (temp[j] < uglyNum[i])
                {
                    minNum = temp[j];
                    uglyNum[i] = temp[j];
                    minj = j;
                }
            }
            for (int j = minj; j < len; ++j)
            {
                if (minNum == temp[j])
                ++index[j];
            }
        }
        return uglyNum[n - 1];
    }  
};

四. 小結

事實上，使用這種方法最少只需不到10行代碼，為了省略一些運算，便用了更多的輔助內存。