成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Super Ugly Number

wuyumin / 2166人閱讀

摘要：建兩個(gè)新數(shù)組，一個(gè)存數(shù)，一個(gè)存。數(shù)組中所有元素初值都是。實(shí)現(xiàn)的過程是，一個(gè)循環(huán)里包含兩個(gè)子循環(huán)。兩個(gè)子循環(huán)的作用分別是，遍歷數(shù)組與相乘找到最小乘積存入再遍歷一次數(shù)組與的乘積，結(jié)果與相同的，就將加，即跳過這個(gè)結(jié)果相同結(jié)果只存一次。

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

建兩個(gè)新數(shù)組，一個(gè)存ugly數(shù)，一個(gè)存index。ugly數(shù)從1開始，后面的是只包含于primes[]中因數(shù)的乘積，如例子中取n = 9，則ugly = [1, 2, 4, 7, 8, 13, 14, 16, 19]，ugly[8] = 19。index數(shù)組中所有元素初值都是0。

實(shí)現(xiàn)的過程是，一個(gè)for循環(huán)里包含兩個(gè)子循環(huán)。看上去不是很容易理解。簡而言之，對i來說，每個(gè)循環(huán)給ugly[i]賦值。兩個(gè)子循環(huán)的作用分別是，遍歷primes數(shù)組與ugly[index[j]]相乘找到最小乘積存入ugly[i]；再遍歷一次primes數(shù)組與ugly[index[j]]的乘積，結(jié)果與ugly[i]相同的，就將index[j]加1，即跳過這個(gè)結(jié)果（相同結(jié)果只存一次）。

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];
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65638.html

相關(guān)文章

  • 264. Ugly NumberII & 313. Super Ugly Number

    摘要：題目解答這個(gè)問題最主要的就是如果按順序找出那么我們?nèi)绻芟氲桨岩詾橐蜃拥倪@些分成三個(gè)然后在每次輸出時(shí)取里最小的那個(gè)數(shù)輸出就可以解決了。 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 評論0 收藏0

  • 264. Ugly Number II & 313. Super Ugly Number

    摘要：每次出一個(gè)數(shù)，就把這個(gè)數(shù)的結(jié)果都放進(jìn)去。，指針從個(gè)變成個(gè)。的做法參考還是復(fù)雜度的問題，回頭再看看 264. Ugly Number II 題目鏈接：https://leetcode.com/problems... dp的方法參考discussion：https://discuss.leetcode.com/... dp的subproblem是：dp[i]: i-th ugly numb...

    hiyang 評論0 收藏0

  • Leetcode[313] Super Ugly Number

    摘要：滾動求最大值復(fù)雜度考慮一個(gè)，的值是下一個(gè)可能的替補(bǔ)值。思路數(shù)組中保存的是之前保留到的值，因?yàn)橄乱粋€(gè)可能的值是和之前的值的倍數(shù)關(guān)系。 Leetcode[313] Super Ugly Number Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whos...

    Aklman 評論0 收藏0

  • leetcode-313-Super Ugly Number

    摘要：題意找出以某些數(shù)為公因數(shù)的遞增排序的第個(gè)數(shù)條件維護(hù)了的元素的相乘因素的。由于是最小值，所以每次保留最小的。問題轉(zhuǎn)化，多次迭代，變成，處理對象變了。不重復(fù)的思想找出重復(fù)計(jì)算的地方，找出不重復(fù)計(jì)算的方法，用極值約束，加以記錄。 題意：找出以某些數(shù)為公因數(shù)的 遞增排序的第n個(gè)數(shù) 條件：indexes 維護(hù)了 primes的元素的相乘因素（uglies）的index。 思路：每次從 prim...

    張春雷 評論0 收藏0

  • [LintCode/LeetCode] Single Number I & II [位運(yùn)算]

    摘要：整個(gè)過程相當(dāng)于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現(xiàn)過一次的，而出現(xiàn)兩次的都在里，出現(xiàn)三次的都被消去了。 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 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<