LeetCode 264 Ugly Number II

LeetCode

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

 

Example 1:

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

 

Constraints:

• 1 <= n <= 1690

题目大意：

求第n个丑数，丑数是由2,3,5相乘获得

Heap算法思路(推荐)：

Heap

注意事项：

1. 与BFS模板一样，visited要在if里面。可以理解为一个数有三条边产生三个新数，所以和BFS模板一样

Python代码：

def nthUglyNumber(self, n: int) -> int:
	heap, visited = [1], set([1])
	primes = [2, 3, 5]
	res = 0
	while n >= 1:
		res = heappop(heap)
		for factor in primes:
			tmp = factor * res
			if tmp not in visited:
				heappush(heap, tmp)
				visited.add(tmp)
		n -= 1
	return res

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n).

---

双指针算法II解题思路：

比较难想，不推荐，但思路可用于其他题如L373。指针的数乘以指向数组的数，此题中指针为p2, p3, p5, 分别代表2， 3， 5， 数组为res数组，每次比较它们的积。

注意事项：

1. 与上题一样要去重，此时，3个乘积中可能会相同且最小，同时移动这些指针

Python代码：

def nthUglyNumber(self, n: int) -> int:
        res = [1]
        p2, p3, p5 = 0, 0, 0
        while n > 1:
            num = min(2 * res[p2], 3 * res[p3], 5 * res[p5])
            if num == 2 * res[p2]:
                p2 += 1
            if num == 3 * res[p3]:
                p3 += 1
            if num == 5 * res[p5]:
                p5 += 1
            res.append(num)
            n -= 1
        return res[-1]

算法分析：

时间复杂度为O(n)，空间复杂度O(n).