313. Super Ugly Number.md

313. Super Ugly Number

思路

此题要求第n个超级丑陋的数, 与264. Ugly Number II.md是类似的, 只是这里质数可以任意给定, 加大了难度, 但本质是一样的. 大致思路就是直接从给定的质数构造ugly数, 可参见264 题解.

思路一

在求k个候选值的最小值时, 可以采用直接遍历一遍的思路, 这样总的复杂度就是O(kn).

STL中min_element和max_element可以求一个vector的最小/大值, 返回的是迭代器.

思路二

当k比较大时候思路一就显得可优化了, 我们可以维护一个大小为k的候选值最小堆, 每个元素包含两个域: value和idx, 分别代表值和由哪一个质数得来, 可以用pair实现.

每当我们从堆顶pop出一个元素, 这个元素的value就是下一个丑陋的数(注意可能重复), 这个元素的idx就代表从哪一个质数得来, 应该将该质数的idx加一, 再向堆中插入下一个候选值. 由于向堆中插入和pop都是对数级别的, 所以总的时间复杂度就是O(nlogk). (但亲测慢很多)

注意学习pair以及priority_queue的用法.

更新:

思路二改进

思路二会比思路一慢很多, 应该有两个原因:

1. 测试样例的k不是很大;
2. 因为堆里面包含大量重复元素, 所以while循环不止执行n次, 所以复杂度应该不止O(nlogk).

所以我们考虑让重复值不要进入堆, 网上只找到了代码没有解释, 代码我也没咋看懂, 这里只给出代码, 有空了再好好想想.

亲测会比思路二快很多.

C++

思路一

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int>nums(n, INT_MAX), candidate(primes.begin(), primes.end()), idx(n, 0);
        nums[0] = 1;
        for(int i = 1; i < n; i++){
            // nums[i] = *min_element(candidate.begin(), candidate.end());
            for(int &c: candidate) nums[i] = min(nums[i], c);
            
            for(int j = 0; j < primes.size(); j++)
                if(candidate[j] == nums[i])
                    candidate[j] = nums[++idx[j]] * primes[j];
        }
        return nums.back();
    }
};

思路二

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> nums(n, INT_MAX), idx(prime_n, 0);
        nums[0] = 1;
        
        int prime_n = primes.size();
        // value, produce_by_which_prime
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> minheap;
        for(int i = 0; i < prime_n; i++)
            minheap.push({primes[i], i});
            
        int count = 1;
        while(count < n){
            pair<int, int>next = minheap.top();
            minheap.pop();
            
            if(nums[count - 1] != next.first){
                nums[count] = next.first;
                count++;
            } // 避免重复
            
            idx[next.second]++;
            minheap.push({nums[idx[next.second]] * primes[next.second], next.second});
        }
        return nums.back();
    }
};

思路二改进

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int prime_n = primes.size();
        vector<int>nums(n, 0), idx(prime_n, 0), last_factor(n, 0);
        nums[0] = 1;
        
        // pair: UglyNumber, produce_by_which_prime
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> minheap;
        for(int i = 0; i < prime_n; i++)
            minheap.push({primes[i], i});
       
        for(int i = 1; i < n; i++){
            pair<int, int>next = minheap.top(); minheap.pop();
            nums[i] = next.first;
            last_factor[i] = next.second;
            
            idx[next.second]++;
            // skip duplicates
            while(last_factor[idx[next.second]] > next.second)
                idx[next.second]++;
            
            minheap.push({nums[idx[next.second]] * primes[next.second], next.second});
        }
        for(int a: last_factor) cout << a << " ";
        return nums.back();
    }
};