264. Ugly Number II

LeetCode Math Dynamic Programming Heap

Write a program to find the $n$ -th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 
        is the sequence of the first 10 ugly numbers.

Note:

1 is typically treated as an ugly number.
$n$ does not exceed 1690.

分析¶

这道题目是263. Ugly Number的延伸，要求给出第 $n$ 个丑数。丑数的质因数只包含2，3，5。所以一个丑数可以表示为 $2^{t_2}3^{t_3}5^{t_5}$ ，其中 $t_2,t_3,t_5$ 为自然数。一种最简单的方法是，求出丑数，然后取出前 $n$ 个值。由于不好判断丑数的顺序，所以采用最小二叉堆来保存。算法时间复杂度为 $n\log(n)$ ，因为每添加/删除一个元素的时间复杂度是 $\log(n)$ ，一共有 $n$ 个循环，空间复杂度是 $O(n)$ 。

public int nthUglyNumber(int n) {
    if (n == 1) return 1;
    PriorityQueue<Long> q = new PriorityQueue(); // 注意Long
    q.offer(1l);

    for(int i = 1; i < n; i++) {
        long min = q.poll();
        //去除重复的丑数
        while(!q.isEmpty() && q.peek() == min) q.poll();
        q.offer(min*2);
        q.offer(min*3);
        q.offer(min*5);
    }
    return q.poll().intValue(); // Long -> int
}

使用动态规划能将时间和空间复杂度降低为 $O(n)$ 。将每个质数对应的丑数的位置存储起来，为 $t_2,t_3,t_5$ 。在最开始，丑数为1，即uglyNumber[0] = 1， $t_2,t_3,t_5$ 都为0，然后

uglyNumber[1] = Math.min(uglyNumber[0]*2, uglyNumber[0]*3, uglyNumber[0]*5)，结果是uglyNumber[0]*2, 所以把 $t_2$ 变成1.
继续uglyNumber[2] = Math.min(uglyNumber[1]*2, uglyNumber[0]*3, uglyNumber[0]*5).

public int nthUglyNumber(int n) {
    if (n == 1) return 1;
    int t2 = 0, t3 = 0, t5 = 0; // pointers for 2, 3, 5
    int[] uglyNumber = new int[n];
    uglyNumber[0] = 1;
    for(int i  = 1; i < n ; i ++){
        // 寻找下一个uglyNumber
        uglyNumber[i] = Math.min(uglyNumber[t2] * 2, 
                        Math.min(uglyNumber[t3] * 3, uglyNumber[t5] * 5));
        // uglyNumber来自哪里？将对应的位置+1
        if (uglyNumber[i] == uglyNumber[t2]*2) t2++; 
        if (uglyNumber[i] == uglyNumber[t3]*3) t3++;
        if (uglyNumber[i] == uglyNumber[t5]*5) t5++;
    }
    return uglyNumber[n-1];
}

需要注意的是要更新所有满足uglyNumber[i] == uglyNumber[pos] * prime[j]的位置。例如6, 需要把2，3的指针向前移1位。因为 $2\times 3 = 6, 3\times 2 = 6$ ，不然接下来计算的丑数会出现重复。