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) DP

思路: dp[i]表示第i个ugly number, 由于ugly number只有2, 3, 5这三个factor，当我们要找下一个ugly number时，我们需要取当前ugly number分别乘以2， 3， 5后最小的数，所以我们分别用三个变量index2, index3, index5找到对应的ugly number

class Solution {
    public int nthUglyNumber(int n) {
        int factor2 = 2, factor3 = 3, factor5 = 5;
        int index2 = 0, index3 = 0, index5 = 0;
        int min = Integer.MAX_VALUE;

        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            min = Math.min(factor2, Math.min(factor3, factor5));
            dp[i] = min;

            if (min == factor2) {
                factor2 = 2 * dp[++index2];
            }

            if (min == factor3) {
                factor3 = 3 * dp[++index3];
            }

            if (min == factor5) {
                factor5 = 5 * dp[++index5];
            }
        }
        return dp[n - 1];
    }
}

3. Time & Space Complexity

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