丑数II

发表于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

LeetCode每日一题，264. 丑数 II

先看题目描述

cwqFiT.png

算法和思路

最小堆

这题可使用最小堆实现，初始时堆为空，首先将最小的丑数 1 加入堆，每次取出堆顶元素 x，则 x 是堆中最小堆丑数，然后将 2x，3x，5x 也加入堆，为了避免重复元素的情况，可以使用有序集合实现这个最小堆，避免相同元素多次加入堆中，第 n 次从最小堆中取出的元素即为第 n 个丑数

动态规划

定义数组 dp，dp[i] 就表示第 i + 1 个丑数，初始化 dp[0] = 1

定义三个指针 p2，p3，p5，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针都为 0

状态转移方程：dp[i] = min{dp[p2] * 2，dp[p3] * 3，dp[p5] * 5}，然后分别比较 dp[i] 和 dp[p2] * 2，dp[p3] * 3，dp[p5] * 5 是否相等，若相等的话则将对应指针加 1

正确性说明：当 i > 0 时，对于 dp[i - 1]，可以保证 dp[p2] * 2，dp[p3] * 3，dp[p5] * 5 均大于 dp[i - 1]，而 dp[p2 - 1] * 2，dp[p3 - 1] * 3，dp[p5 - 1] * 5 均小于等于 dp[i - 1]，因此 dp[i - 1] 之后的下一个丑数即 dp[i] 一定出现在 dp[p2] * 2，dp[p3] * 3，dp[p5] * 5 这三个数之中，取其中的最小值即可，然后将对应指针往后移 1 位

算法源码

最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int nthUglyNumber(int n) {
        TreeSet<Long> treeSet = new TreeSet<>();
        treeSet.add(1L);
        for (int i = 1; i < n; i++) {
            long num = treeSet.pollFirst();
            treeSet.add(2 * num);
            treeSet.add(3 * num);
            treeSet.add(5 * num);
        }
        long res = treeSet.first();
        return (int)res;
    }
}

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        for (int i = 1; i < n; i++) {
            int a = dp[p2] * 2;
            int b = dp[p3] * 3;
            int c = dp[p5] * 5;
            int cur = Math.min(Math.min(a, b), c);
            if (cur == a) {
                p2++;
            }
            if (cur == b) {
                p3++;
            }
            if (cur == c) {
                p5++;
            }
            dp[i] = cur;
        }
        return dp[n - 1];
    }
}