ugly number系列

264. Ugly Number II Total Accepted: 45283 Total Submissions: 146066 Difficulty: Medium Contributors: Admin Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:

The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.Show More Hint

整体思路是：第n个ugly number是第n-1个ugly number的[2,3,5]倍，所以用一个min-heap或者array存已有的ugly number。

方法1：用了heapq，O(nlogn)的复杂度。heap中存tuple（当前ugly number，乘数即235中的一个），每次从heap里弹出最小的，用tuple中的fact和2，3，5分别比较，比它小的话就用当前ugly numberfact，再push到heap里。这样就避免了出现重复情况：比如pop出了（5，5），说明当前ugly number是5，是之前的u m5得到的。当5和2，3，5比较时，因为5>2，所以不能52，因为之前25已经算过了，这样会造成重复。

方法2：用了array，O(n)复杂度。array中存所有的ugly number。用last记录上一个u m，三个pointer记录2，3，5因子的位置，同样为了避免重复，当res[p2]*2<=last时，说明这个ugly number已经算过了，将p2的位置前进一个。以此类推。当3个因子的位置都调整完之后，res array加入新得到number中的最小一个，这样就能保证array的顺序。

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        # h = [(1,1)]
        # for i in range(n):
        #     val, fact = heapq.heappop(h)
        #     for each in 2,3,5:
        #         if fact <= each:
        #             heapq.heappush(h, (val * each, each))
        # return val

        res = [1]
        p2,p3,p5 = 0, 0, 0
        for i in range(1,n):
            last = res[i-1]
            while res[p2] * 2 <= last:
                p2 += 1
            while res[p3] * 3 <= last:
                p3 += 1
            while res[p5] * 5 <= last:
                p5 += 1
            res.append(min(res[p2] * 2, res[p3] * 3, res[p5] * 5))
        return res[-1]