Ugly Number

Source

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.

题解

这是丑数问题（Ugly Number）, 思路参看：

http://www.cppblog.com/zenliang/articles/131094.html

http://www.geeksforgeeks.org/ugly-numbers/

分析：假设数组ugly[N]中存放不断产生的丑数，初始只有一个丑数ugly[0]=1，由此出发，下一个丑数由因子2,3,5竞争产生，得到ugly[0]2, ugly[0]3, ugly[0]5， 显然最小的那个数是新的丑数，所以第2个丑数为ugly[1]=2，开始新一轮的竞争，由于上一轮竞争中，因子2获胜，这时因子2应该乘以ugly[1]才显得公平，得到ugly[1]2,ugly[0]3,ugly[0]5， 因子3获胜，ugly[2]=3，同理，下次竞争时因子3应该乘以ugly[1]，即：ugly[1]2, ugly[1]3, ugly[0]*5, 因子5获胜，得到ugly[3]=5，重复这个过程，直到第n个丑数产生。总之：每次竞争中有一个（也可能是两个）因子胜出，下一次竞争中 胜出的因子就应该加大惩罚！

注意这里不可以使用if/else 循环，因为有可能多于一个指针的结果是相等的：例如p3->5, p5->3, 他们的结果相等，这是两个指针都要+1

Java

//第一种方法 dynamic programming O(k)

class Solution {
    /**
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    public long kthPrimeNumber(int k) {
        long[] res = new long[k+1];
        res[0] = 1;
        int k3 = 0, k5 = 0, k7 = 0;
        for (int i=1; i<=k; i++) {
            res[i] = Math.min(Math.min(res[k3]*3, res[k5]*5), res[k7]*7);
            if (res[i]/res[k3] == 3) k3++;
            if (res[i]/res[k5] == 5) k5++;
            if (res[i]/res[k7] == 7) k7++;
        }
        return res[k];
    }
};