264. Ugly Number II.md

title	toc	date	tags	top
264. Ugly Number II	false	2017-10-30	LeetCode Math Dynamic Programming Heap	264

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$，不然接下来计算的丑数会出现重复。