Ugly Number II

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

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Example

If n=9, return 10.

Solution

(1) DP O(n)

the key is there are 3 indexing as a jumper.

(2) Priority Queue O(klogk)

heapq.heappop , pop the min value int he queue.

while from 0 to N

while level < 3

push

这里让我们找到第n个丑陋数，还好题目中给了很多提示，基本上相当于告诉我们解法了，根据提示中的信息，我们知道丑陋数序列可以拆分为下面3个子列表：

(1) 1×2, 2×2, 3×2, 4×2, 5×2, …

(2) 1×3, 2×3, 3×3, 4×3, 5×3, …

(3) 1×5, 2×5, 3×5, 4×5, 5×5, …

(3) 解题思路：

参考：http://www.geeksforgeeks.org/ugly-numbers/

丑陋数序列可以拆分为下面3个子列表：

(1) 1×2, 2×2, 3×2, 4×2, 5×2, …

(2) 1×3, 2×3, 3×3, 4×3, 5×3, …

(3) 1×5, 2×5, 3×5, 4×5, 5×5, …

我们可以发现每一个子列表都是丑陋数本身(1, 2, 3, 4, 5, …) 乘以 2, 3, 5

接下来我们使用与归并排序相似的合并方法，从3个子列表中获取丑陋数。每一步我们从中选出最小的一个，然后向后移动一步。

http://bookshadow.com/weblog/2015/08/19/leetcode-ugly-number-ii/

class Solution:
    """
    @param {int} n an integer.
    @return {int} the nth prime number as description.
    """
    def nthUglyNumber(self, n):
        f = [0] * n
        f[0] = 1
        index2 = index3 = index5 = 0
        minValue = 0
        for i in range(1, n):
            f[i] = min(f[index2] * 2, f[index3] * 3, f[index5] * 5)
            if f[i] == f[index2] * 2 :
                index2 += 1
            if f[i] == f[index3] * 3 :
                index3 += 1
            if f[i] == f[index5] * 5 :
                index5 += 1
        return f[-1]

    def nthUglyNumber2(self, n):
        q = [1]
        i2 = i3 = i5 = 0
        while len(q) < n:
            m2, m3, m5 = q[i2] * 2, q[i3] * 3, q[i5] * 5
            m = min(m2, m3, m5)
            if m == m2:
                i2 += 1
            if m == m3:
                i3 += 1
            if m == m5:
                i5 += 1
            q += m,
        return q[-1]