[LintCode/LeetCode] Super Ugly Number

wuyumin 发布于2019-08-14 15:20 / 2127人阅读

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

Problem

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.

Notice

1 is a super ugly number for any given primes.
The given numbers in primes are in ascending order.
0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000

Example

Given n = 6, primes = [2, 7, 13, 19] return 13

Note

建两个新数组，一个存ugly数，一个存index。ugly数从1开始，后面的是只包含于primes[]中因数的乘积，如例子中取n = 9，则ugly = [1, 2, 4, 7, 8, 13, 14, 16, 19]，ugly[8] = 19。index数组中所有元素初值都是0。

实现的过程是，一个for循环里包含两个子循环。看上去不是很容易理解。简而言之，对i来说，每个循环给ugly[i]赋值。两个子循环的作用分别是，遍历primes数组与ugly[index[j]]相乘找到最小乘积存入ugly[i]；再遍历一次primes数组与ugly[index[j]]的乘积，结果与ugly[i]相同的，就将index[j]加1，即跳过这个结果（相同结果只存一次）。

Solution

public class Solution {
    public  int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
        int[] index = new int[primes.length];
        ugly[0] = 1;
        for (int i = 1; i < n; i++) {
        //find next
            ugly[i] = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j++)
                ugly[i] = Math.min(ugly[i], primes[j] * ugly[index[j]]);
        //slip duplicate
            for (int j = 0; j < primes.length; j++) {
                while (primes[j] * ugly[index[j]] == ugly[i]) index[j]++;
            }
        }
        return ugly[n - 1];
    }
}

云服务器 GPU云服务器 Ugly super python中super java super编译器

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

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

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

摘要：滚动求最大值复杂度考虑一个，的值是下一个可能的替补值。思路数组中保存的是之前保留到的值，因为下一个可能的值是和之前的值的倍数关系。 Leetcode[313] Super Ugly Number Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whos...

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

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

张春雷 2019-07-30 17:35 评论0 收藏0
[LintCode/LeetCode] Single Number I & II [位运算]

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 评论0 收藏0