pylist

4. Ugly Number II

Ugly number is a number that only have prime 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 1:

Input: 9
Output: 10

Example 2:

Input: 1
Output: 1
Challenge
O(n log n) or O(n) time.

Notice: Note that 1 is typically treated as an ugly number.

Binary search Solution

O(nlogn) 的复杂度

class Solution:
    """
    @param n: An integer
    @return: return a  integer as description.
    """
    def nthUglyNumber(self, n):
        nums = [1, 2, 3, 4, 5]
        if n <= len(nums):
            return nums[n-1]
            
        while len(nums) < n:
            candi = []
            for f in [2, 3, 5]:
                up = len(nums)-1
                low = 0
                # bi-search to find the lowest i that
                # nums[i] * f > num[-1]
                while up - low > 1:
                    mid = low + (up - low) // 2
                    # if condition satisfied
                    if nums[mid] * f > nums[-1]:
                        up = mid
                    else:
                        low = mid
                candi.append(nums[up] * f)
            nums.append(min(candi))
            
        return nums[-1]

Heap solution

from heapq import heappush, heappop
class Solution:
    """
    @param n: An integer
    @return: return a  integer as description.
    """
    def nthUglyNumber(self, n):
        if n == 1:
            return 1
            
        nums = [1]
        h = []
        pushed = set()
        while len(nums) < n:
            for f in [2, 3, 5]:
                candi = nums[-1] * f
                if candi not in pushed:
                    heappush(h, candi)
                    pushed.add(candi)
            nums.append(heappop(h))
        return nums[-1]