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

题目地址: leetcode Super Ugly Number

题意:

给定因子Primes , 让你求第n个super ugly number。

super ugly number定义为:整数,且因子全部都在primes中。 注意1为特殊的super ugly number。

思路:

和 leetcode Ugly Number  II 思路一样,要使得super ugly number 不漏掉,那么用每个因子去乘第一个,当前因子乘积是最小后,乘以下一个…..以此类推。

 

C++ 

Java 

Python

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Super Ugly Number
本文地址:https://www.hrwhisper.me/leetcode-super-ugly-number/

听说长得好看的已经打赏了

Leetcode . permalink.

3 thoughts on “leetcode Super Ugly Number

  1. 请问这个算的的时间复杂度是多少呢?我感觉是O(NlogK)但是这个执行时间比O(nk)长很多。
    int nthSuperUglyNumber(int n, vector& primes) {
    const size_t k = primes.size();
    vector uglyNum(n, INT_MAX);
    uglyNum[0] = 1;
    vector next(k, 0), next_i(k, 0);
    for(int i = 0; i < k; ++i)
    next[i] = primes[i];
    for(int i = 1; i < n; ++i){
    for(int j = 0; j < k; ++j)
    uglyNum[i] = min(uglyNum[i], next[j]);
    for(int j = 0; j < k; ++j)
    if(uglyNum[i] == next[j])
    next[j] = primes[j] * uglyNum[++next_i[j]];
    }
    return uglyNum[n – 1];
    }

    • 对的,我用的优先队列,是O(NlogK),但是比直接的O(nk)慢,我感觉是因为是使用了自定义的类Node, 比简单的方法要慢,而数据量小,复杂度优势体现不出来。T^T

Leave a Reply

Your email address will not be published. Required fields are marked *