Ugly Number

Ugly number is a number that only have factors 3, 5 and 7.

Design an algorithm to find the Kth ugly number. The first 5 ugly numbers are 3, 5, 7, 9, 15 ...

Example

If K=4, return 9.

Challenge: O(K log K) or O(K) time.

动态规划

复杂度:时间 O(N) 空间 O(N)

解题思路：要得到第N个丑陋数，最直接的想法就是从1开始递增循环，直到找到第N个丑陋数，但是这样明显开销太大，而且我们没有用到已经生成的丑陋数的信息。如果有一个方法能够顺序只生成丑陋数就好了。仔细观察可以发现，丑陋数的因子也必定是丑陋数，它一定是某个丑陋数乘3、5、7得到的。但问题在于，小的丑陋数乘5不一定比大的丑陋数乘3要小，我们没法直接使用目前最大的丑陋数来乘3、5、7顺序得到更大的丑陋数。不过，我们可以确定的是，小的丑陋数3，肯定小于大的丑陋数乘3。所以我们使用三个指针，分别记录乘3、5、7得出的目前最大丑陋数，这样我们通过比较这三种最大丑陋数（这里最大是相对于只乘3、只乘5、只乘7三种不同情况下最大的丑陋数），就得到了所有数里最大的丑陋数。

public int nthUglyNumber(int n) {
    List<Integer> res = new ArrayList<Integer>();
    res.add(1);
    int i3 = 0, i5 = 0, i7 = 0;

    while(res.size() < n+1){
        int m3 = res.get(i3) * 3;
        int m5 = res.get(i5) * 5;
        int m7 = res.get(i7) * 7;
        int min = Math.min(m3, Math.min(m5, m7));

        res.add(min);
        if(min == m3) i3++;
        if(min == m5) i5++;
        if(min == m7) i7++;
    }
    return res.get(res.size()-1);
}