LeetCode_Heap_313. Super Ugly Number 超級醜數【堆逾時，動态規劃】【C++】【中等】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​三，AC代碼​​

​​C++​​

​​四，解題過程​​

​​第一博​​

​​第二搏​​

一，題目描述

英文描述

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nth super ugly number.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

中文描述

超級醜數 是一個正整數，并滿足其所有質因數都出現在質數數組 primes 中。

給你一個整數 n 和一個整數數組 primes ，傳回第 n 個 超級醜數 。

題目資料保證第 n 個 超級醜數 在 32-bit 帶符号整數範圍内。

示例與說明

二，解題思路

這一題的測試用例比較複雜，采用堆的方法容易逾時。這裡采用動态規劃的方法。

每挑選出一個醜數，更新指針對應的下一個醜數并存放在數組中，避免重複計算。

三，AC代碼

C++

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> index(primes.size(), 0);
        vector<long> nums(primes.size(), 1);// 記錄每個指針計算出的對應醜數
        vector<int> ans;// 存放最終標明的醜數數組

        for (int j = 0; j < n; j++) {
            int minNum = INT_MAX;
            for (int i = 0; i < primes.size(); i++) {
                if (nums[i] < minNum) {
                    minNum = nums[i];
                }
            }
            ans.push_back(minNum);
            for (int i = 0; i < index.size(); i++) {
                if (nums[i] == minNum) {
                    nums[i] = long(primes[i]) * ans[index[i]];// 更新
                    index[i]++;// 更新
                }
            }
        }
        return ans[n - 1];
    }
};      

四，解題過程

第一博

按照之前的思路，寫出來個動态規劃版的解法，然而逾時了。。。

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> index(primes.size(), 0);
        vector<int> ans;
        ans.push_back(1);
        int num = n;

        while (--num) {
            int minNum = INT_MAX;
            for (int i = 0; i < primes.size(); i++) {
                int cur = primes[i] * ans[index[i]];
                if (cur < minNum) {
                    minNum = cur;
                }
            }
            ans.push_back(minNum);
            for (int i = 0; i < index.size(); i++) {
                if (primes[i] * ans[index[i]] == minNum) {
                    index[i]++;
                }
            }
        }
        return ans[n - 1];
    }
};      

第二搏

可以看出上面的方法中重複計算了乘法的過程，這裡把計算的結果保留下來，避免重複計算：

稍微操作一下，儲存之前計算過的資料。由于資料太大需要用long類型。