超级丑数

题意

写一个程序来找第 n 个超级丑数。

超级丑数的定义是正整数并且所有的质数因子都在所给定的一个大小为 k 的质数集合内。

比如给你 4 个质数的集合 [2, 7, 13, 19], 那么 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 是前 12 个超级丑数。

注意事项

  • 1 永远都是超级丑数不管给的质数集合是什么。
  • 给你的质数集合已经按照升序排列。
  • 0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000

样例

给出 n = 6 和质数集合 [2, 7, 13, 19]。第 6 个超级丑数为 13,所以返回 13 作为结果。

思路

这道题其实就是丑数II 的加强版,只是原来的丑数定义质因子是固定的 3 个,现在是自定义的质因子。

只需要将 丑数II 中的 lastUgly 用数组存放起来即可,其他思路还是一样的。

代码实现

public class Solution {
    /**
     * @param n a positive integer
     * @param primes the given prime list
     * @return the nth super ugly number
     */
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] uglys = new int[n];
        int[] idxPrimes = new int[primes.length];
        uglys[0] = 1;
        
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            
            for (int j = 0; j < primes.length; j++) {
                min = Math.min(min, primes[j] * uglys[idxPrimes[j]]);
            }
            uglys[i] = min;
            
            for (int j = 0; j < primes.length; j++) {
                if (primes[j] * uglys[idxPrimes[j]] == min) {
                    idxPrimes[j]++;                    
                }
            }
        }
        return uglys[n - 1];
    }
}

原题地址

LintCode:超级丑数

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 丑数II

    一份执着✘
  • LeetCode 26 Remove Duplicates from Sorted Array

    一份执着✘
  • 删除排序数组中的重复数字Ⅱ

    一份执着✘
  • AI 技术讲座精选:菜鸟学深度学习(一)

    【AI100 导读】在本系列中,你将会学习如何利用深度学习解决那些比较简单的问题。在解决问题的过程中,你不仅会学到深度学习中的某一种类型,也可以在 Keras ...

    AI科技大本营
  • 查找算法常见的五大面试知识点与两类实战!

    查找(Search),又称为搜索,指从数据表中找出符合特定条件的记录。如今我们处在信息爆炸的大数据时代,如何从海量信息中快速找到需要的信息,这就需要查找技术。如...

    Datawhale
  • “万维网之父”发文阐述其下一个网络时代:将数据与应用分离,互联网去中心化正在路上

    关注“万维网之父”Tim Berners-Lee 动态的人,一定知道这位业内大神正在投身于下一代互联网的建设——一个去中心化的互联网。

    钱塘数据
  • 自然语言处理之hanlp,Python调用与构建,分词、关键词提取、命名主体识别

    HanLP是一系列模型与算法组成的NLP工具包,由大快搜索主导并完全开源,目标是普及自然语言处理在生产环境中的应用。HanLP具备功能完善、性能高效、架构清晰、...

    学到老
  • 删除排序数组中的重复数字Ⅱ

    一份执着✘
  • 团体程序设计天梯赛-练习集 L1-016 查验身份证

    一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下:

    C you again 的博客
  • 字符串问题-LeetCode 392、383、386、384、396、937(字符串)

    你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券