超级丑数

313. 超级丑数

难度中等153收藏分享切换为英文接收动态反馈

编写一段程序来查找第 *n* 个超级丑数。

超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

示例:

输入: n = 12, primes = [2,7,13,19]
输出: 32 
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

说明:

• 1 是任何给定 primes 的超级丑数。
• 给定 primes 中的数字以升序排列。
• 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
• 第 n 个超级丑数确保在 32 位有符整数范围内。

通过次数15,070

提交次数23,597

暴力求解(超时)

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        if(n==1)return 1;
        int cnt=1;
        int i=2;
        while(cnt<n){
            int val=i;
            for(int j=0;j<primes.length;j++){
                while(val%primes[j]==0){
                    val/= primes[j];
                }
            }
            //System.out.println(i);
            if(val==1)cnt++;
            if(cnt<n)i++;
        }
        return i;
    }

}

最小优先队列

优先队列数组中的第一个元素是丑数、第二个元素是基于哪一个丑数计算而来、第三个元素记录了基于哪一个质因子计算而来

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0]-o2[0]);//lambda表达式。以数组的第一个元素升序排序。
        // 把原来的加进去
        for(int i=0;i<primes.length;i++) pq.add(new int[]{primes[i],0,i});
        
        for (int i = 1; i < n; i++) {
            int[] tmp = pq.poll();
            // tmp[0]存储的是当前的丑数
            ugly[i] = tmp[0];
            // tmp[1]存储的是从哪个丑数计算而来,tmp[2]存储的是从那个质数因子计算而来
            // 把原先的丑数后移一个
            tmp[0] = ugly[++tmp[1]]*primes[tmp[2]];//tmp[1]和tmp[2]分别为丑数和质因子的索引。
            pq.add(tmp);
            if(ugly[i]==ugly[i-1]) i--;//如果ugly[i]和ugly[i-1]重复了，那就再重新计算一次ugly[i]。
        }
        return ugly[n - 1];
    }
}

作者：lora-h
链接：https://leetcode-cn.com/problems/super-ugly-number/solution/zui-xiao-you-xian-dui-lie-dai-ma-hao-li-plfja/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int [] dp=new int[n];
        dp[0]=1;

        int k=primes.length;
        int []index=new int[k];



        for(int i=1;i<n;i++){
            int min=Integer.MAX_VALUE;
            for(int j=0;j<k;j++){
                if(min>dp[index[j]]*primes[j]){
                    min=dp[index[j]]*primes[j];
                }
            }
            dp[i]=min;
            //滑动index
            for(int j=0;j<k;j++){
                if(min==dp[index[j]]*primes[j]){
                    index[j]++;
                }
            }
        }
        return dp[n-1];
    }
}




作者：akian
链接：https://leetcode-cn.com/problems/super-ugly-number/solution/313-chao-ji-chou-shu-dui-by-akian/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信