264. 丑数 II

Difficulty

Medium

法1 优先队列（小根堆）

思路

根据丑数的定义，我们有如下结论：

1 是最小的丑数。

对于任意一个丑数，其与任意的质因数（2、3、5）相乘，结果（2x、3x、5x）仍为丑数。

有了基本的分析思路，一个简单的解法是使用优先队列：

起始先将最小丑数放入队列

每次从队列取出最小值，然后将所对应的丑数、和进行入队。

对步骤 2 循环多次，第次出队的值即是答案。

为了防止同一丑数多次进队，我们需要使用数据结构 set() 来记录入过队列的丑数。

题解


import heapq
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        hash_set = set()

        heap = []
        heapq.heappush(heap, 1)
        hash_set.add(1)

        for i in range(0, n):
            cur = heapq.heappop(heap)
            if i == n-1:
                return cur

            for num in [2, 3, 5]:
                temp = cur * num
                if temp not in hash_set:
                    hash_set.add(temp)
                    heapq.heappush(heap, temp)

        return -1

多路归并（多指针）

从解法一中不难发现，我们「往后产生的丑数」都是基于「已有丑数」而来（使用「已有丑数」乘上「质因数」2、3、5）。

因此，如果我们所有丑数的有序序列为a_1, a_2, a_3, ..., a_n 的话，序列中的每一个数都必然能够被以下三个序列（中的至少一个）覆盖：

由丑数 * 2 所得的有序序列：1*2, 2*2, 3*2, ...

由丑数 * 3 所得的有序序列：1*3, 2*3, 3*3, ...

由丑数 * 5 所得的有序序列：1*5, 2*5, 3*5, ...

因此我们可以使用三个指针来指向目标序列 arr 的某个下标（下标作为哨兵不使用，起始都为1），使用arr[下标] * 质因数代表当前使用到三个有序序列中的哪一位，同时使用idx表示当前生成到arr哪一位丑数。


import heapq
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        res = [0] * (n+1)
        res[1] = 1

        i2, i3, i5 = 1, 1, 1
        for idx in range(2, n+1):
            a, b, c = res[i2] * 2, res[i3]*3, res[i5]*5
            val = min(a, b, c)
            res[idx] = val
            if a == val:
                i2 += 1
            if b == val:
                i3 += 1
            if c == val:
                i5 += 1
                
        return res[-1]