Ugly Number

Question

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 ...

Thoughts

ugly number

这一题跟之前的ugly number不太一样，只有3,5,7， 之前的题是说prime factor只有2,3,5

分析：假设数组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个丑数产生。

总之：每次竞争中有一个（也可能是两个）因子胜出，下一次竞争中 胜出的因子就应该加大惩罚！

我的理解是，每次的值肯定是从之前的数中得出，但是3,5,7所用的数不一样，所以要有三个pointer,然后在上一次比较中最小的数因为对于这个乘数已经用过了，所以应该跳过，指向下一个数

Analysis

Solution

class Solution:
    """
    @param k: The number k.
    @return: The kth prime number as description.
    """
    def kthPrimeNumber(self, k):
        # write your code here
        if not k:
            return None
        indexThree = 0
        indexFive = 0
        indexSeven = 0
        result = []
        result.append(1)

        for i in range(1, k + 1):
            newNum = min(result[indexThree] * 3, result[indexFive] * 5, result[indexSeven] * 7)
            result.append(newNum)
            if newNum / result[indexThree] == 3:
                indexThree += 1
            if newNum / result[indexFive] == 5:
                indexFive += 1
            if newNum / result[indexSeven] == 7:
                indexSeven += 1
        return result[k]