Daily LeetCode 264. Ugly Number II

https://leetcode.com/problems/ugly-number-ii/

Medium

问题描述

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

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.

Note:

1. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

Hint1

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.

Hint2

An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.

Hint3

The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: $L_1,L_2,L_3$

Hint4

Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

思路及代码

题目给出了ugly number的定义：质因数仅为2、3、5的数，同时，1也被看作是ugly number，我们需要找出第n个ugly number。

这一题显然不能够用暴力解法一个个找，题目中的提示已经给出了解法，所有的ugly number都应该由一个小的丑陋数序列乘2、3或5得到，因此，丑陋数序列可以拆分为三个子序列：

1. ==1x2==, 2x2, ==2x2==, 3x2, ==3x2==, 4x2, ……
2. 1x3, ==1x3==, 2x3, 2x3, 2x3, ==2x3==, ……
3. 1x5, 1x5, 1x5, ==1x5==, 2x5, 2x5, ……

我们依次在三个子序列中找到当前最小的丑陋数，将其加到res数组中，这样就能够形成一个递增的丑陋数序列。

代码如下：

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        res = [1]
        index2, index3, index5 = 0, 0, 0

        while len(res) < n:
            multi2, multi3, multi5 = res[index2] * 2, res[index3] * 3, res[index5] * 5
            min_multi = min(multi2, multi3, multi5)
            if min_multi == multi2: index2 += 1
            if min_multi == multi3: index3 += 1
            if min_multi == multi5: index5 += 1
            res.append(min_multi)

        return res[-1]