丑数II

[PisecesPeng]

丑数II

给你一个整数n, 请你找出并返回第n个丑数.

丑数就是只包含质因数2、3和/或5的正整数.

示例 1: 

输入: n = 10
输出: 12
解释: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前10个丑数组成的序列.

示例 2: 

输入: n = 1
输出: 1
解释: 1 通常被视为丑数.

提示:

• 1 <= n <= 1690

题目地址: https://leetcode-cn.com/problems/ugly-number-ii/

[PisecesPeng]

解题思路

• dp数组, 数值滚动到对应的下标即可;

代码

private static int func(int n) {
    int a = 0, b = 0, c = 0;
    int[] dp = new int[n];
    dp[0] = 1;
    for(int i = 1; i < n; i++) {
        int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
        dp[i] = Math.min(Math.min(n2, n3), n5);
        if(dp[i] == n2) a++;
        if(dp[i] == n3) b++;
        if(dp[i] == n5) c++;
    }
    return dp[n - 1];
}

[PisecesPeng]

LeetCode题解

解题思路

• 构建最小堆;
• 演算符合'丑数'要求的数字, 去重后加入堆;
• 依次从最小堆中取出数字;

代码

private static int func(int n) {
    int[] factors = {2, 3, 5};
    Set<Long> seen = new HashSet<Long>();
    PriorityQueue<Long> heap = new PriorityQueue<Long>();
    seen.add(1L);
    heap.offer(1L);
    int ugly = 0;
    for (int i = 0; i < n; i++) {
        long curr = heap.poll();
        ugly = (int) curr;
        for (int factor : factors) {
            long next = curr * factor;
            if (seen.add(next)) {
                heap.offer(next);
            }
        }
    }
    return ugly;
}

[PisecesPeng]

LeetCode题解

解题思路

• dp数组, 数值滚动到对应的下标即可;

代码

private static int func(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1;
    for (int i = 2; i <= n; i++) {
        int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
        dp[i] = Math.min(Math.min(num2, num3), num5);
        if (dp[i] == num2) {
            p2++;
        }
        if (dp[i] == num3) {
            p3++;
        }
        if (dp[i] == num5) {
            p5++;
        }
    }
    return dp[n];
}