264. Ugly Number II

Priority Queue

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 {
    private static final int[] NUMS = new int[]{2, 3, 5};

    public int nthUglyNumber(int n) {
        Set<Long> set = new HashSet<>();
        Queue<Long> queue = new PriorityQueue<>();

        set.add(1L);
        queue.offer(1L);

        for (int i = 1; i <= n; i++) {
            long x = queue.poll();
            if (i == n) {
                return (int) x;
            }

            for (long num : NUMS) {
                if (set.add(x * num)) {
                    queue.offer(x * num);
                }
            }
        }

        return -1;
    }
}

DP

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 + 1];
        dp[1] = 1;

        // 最后一个乘以 2/3/5 的元素的索引
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int product2 = dp[p2] * 2, product3 = dp[p3] * 3, product5 = dp[p5] * 5;
            int uglyNum = Math.min(product2, Math.min(product3, product5));
            if (product2 == uglyNum) {
                p2++;
            }
            if (product3 == uglyNum) {
                p3++;
            }
            if (product5 == uglyNum) {
                p5++;
            }

            dp[i] = uglyNum;
        }

        return dp[n];
    }
}

References

264. Ugly Number II
剑指 Offer 49. 丑数
面试题 17.09. 第 k 个数
三指针方法的理解方式