Leetcode[313] Super Ugly Number

Aklman 发布于2019-08-16 10:27 / 2073人阅读

摘要：滚动求最大值复杂度考虑一个，的值是下一个可能的替补值。思路数组中保存的是之前保留到的值，因为下一个可能的值是和之前的值的倍数关系。

Leetcode[313] 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.

滚动求最大值

复杂度
考虑一个index，i
primes[index] * res[index[i]]的值是下一个可能的替补值。

思路
int[] res数组中保存的是之前保留到的值，因为下一个可能的值是primes[i]和之前的值的倍数关系。

代码

public int nthSuperUglyNumber(int n, int[] primes) {
    int[] res = new int[n];
    res[0] = 1;
    int[] index = new int[primes.length];
    for(int i = 1; i < n; i ++) {
        res[i] = Integer.MAX_VALUE;
        for(int j = 0; j < primes.length; j ++) {
            res[i] = Math.min(res[i], primes[j] * res[index[j]]);
        }
        //
        for(int j = 0; j < primes.length; j ++) {
            if(primes[j] * res[index[j]] == res[i]) {
                index[j] ++;
            }
        }
    }
    return res[n - 1];
}

混合云 idc机房托管 Ugly V313 super LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69837.html

264. Ugly Number II & 313. Super Ugly Number

摘要：每次出一个数，就把这个数的结果都放进去。，指针从个变成个。的做法参考还是复杂度的问题，回头再看看 264. Ugly Number II 题目链接：https://leetcode.com/problems... dp的方法参考discussion：https://discuss.leetcode.com/... dp的subproblem是：dp[i]: i-th ugly numb...

hiyang 2019-08-16 10:29 评论0 收藏0
leetcode-313-Super Ugly Number

摘要：题意找出以某些数为公因数的递增排序的第个数条件维护了的元素的相乘因素的。由于是最小值，所以每次保留最小的。问题转化，多次迭代，变成，处理对象变了。不重复的思想找出重复计算的地方，找出不重复计算的方法，用极值约束，加以记录。题意：找出以某些数为公因数的递增排序的第n个数条件：indexes 维护了 primes的元素的相乘因素（uglies）的index。思路：每次从 prim...

张春雷 2019-07-30 17:35 评论0 收藏0
leetcode263,264,313 ugly numbers

摘要：这题可以使用暴力遍历法，从开始，对每一个数都进行判断，直到找到第个丑数为止。优先队列可以很好的满足该情况。因此每个素数持有的信息包括当前对应的丑数的下标。前言这一篇博客把ugly numbers系列的题目做一个整理。这三道题正好是一个思路的循序渐进，所以放在一篇博客当中。 Ugly Number Write a program to check whether a given nu...

everfly 2019-08-16 11:02 评论0 收藏0
264. Ugly NumberII & 313. Super Ugly Number

摘要：题目解答这个问题最主要的就是如果按顺序找出那么我们如果能想到把以为因子的这些分成三个然后在每次输出时取里最小的那个数输出就可以解决了。 264 Ugly NumberII题目：Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only i...

Lionad-Morotar 2019-08-14 14:06 评论0 收藏0
[LintCode/LeetCode] Super Ugly Number

摘要：建两个新数组，一个存数，一个存。数组中所有元素初值都是。实现的过程是，一个循环里包含两个子循环。两个子循环的作用分别是，遍历数组与相乘找到最小乘积存入再遍历一次数组与的乘积，结果与相同的，就将加，即跳过这个结果相同结果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 评论0 收藏0