264 Ugly Number II

264. Ugly Number II

1. Question

Write a program to find then-th ugly number.

Ugly numbers are positive numbers whose prime factors only include2, 3, 5. For example,1, 2, 3, 4, 5, 6, 8, 9, 10, 12is the sequence of the first10ugly numbers.

Note that1is typically treated as an ugly number, and n does not exceed 1690.

2. Implementation

(1) Heap

class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        minHeap.add(1L);

        long curNum = 0;
        for (int i = 0; i < n; i++) {
            curNum = minHeap.remove();

            while (!minHeap.isEmpty() && minHeap.peek() == curNum) {
                curNum = minHeap.remove();
            }

            minHeap.add(2 * curNum);
            minHeap.add(3 * curNum);
            minHeap.add(5 * curNum);
        }
        return (int)curNum;
    }
}

3. Time & Space Complexity

Heap: 时间复杂度O(n * logn), 空间复杂度O(n)