What is the state transition dynamic programming approach in Ugly Number II?

The state transition dynamic programming approach in Ugly Number II uses multiple pointers to track the next possible ugly numbers for 2, 3, and 5. By updating these pointers, we generate the ugly number sequence efficiently.

Why is a heap used in the Ugly Number II problem?

A heap is used to track the next smallest ugly number by pushing the results of multiplying the current ugly numbers by 2, 3, and 5, which ensures that we can extract the next smallest number efficiently.

How does the Ugly Number II problem relate to dynamic programming?

The Ugly Number II problem uses dynamic programming to keep track of previously computed ugly numbers and efficiently generate the next numbers in the sequence by utilizing a state transition approach.

What are common mistakes when solving Ugly Number II?

Common mistakes include using brute force to check each number for ugliness and failing to manage the state transitions for 2, 3, and 5 correctly.

How can I optimize my solution for large values of n in Ugly Number II?

To optimize for large values of n, focus on space and time efficiency. Use dynamic programming with a heap to manage the sequence generation while ensuring optimal storage and extraction of values.

#264

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

丑数 II

给你一个整数 n ，请你找出并返回第 n 个丑数。丑数就是质因子只包含 2 、 3 和 5 的正整数。示例 1：输入： n = 10 输出： 12 解释： [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。示例 2：输入： n = 1 …

哈希表数学动态规划堆（优先队列）

题目描述

给你一个整数 n ，请你找出并返回第 n 个丑数。

丑数就是质因子只包含 2、3 和 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：

1 <= n <= 1690

lightbulb

解题思路

方法一：优先队列（最小堆）

初始时，将第一个丑数 $1$ 加入堆。每次取出堆顶元素 $x$ ，由于 $2x$ , $3x$ , $5x$ 也是丑数，因此将它们加入堆中。为了避免重复元素，可以用哈希表 $vis$ 去重。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        h = [1]
        vis = {1}
        ans = 1
        for _ in range(n):
            ans = heappop(h)
            for v in [2, 3, 5]:
                nxt = ans * v
                if nxt not in vis:
                    vis.add(nxt)
                    heappush(h, nxt)
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Look for familiarity with dynamic programming and heap-based approaches.
question_mark
Evaluate whether the candidate can optimize space complexity while maintaining time efficiency.
question_mark
Assess how well the candidate can combine multiple data structures (heap, array) to solve a problem.

warning

常见陷阱

外企场景

error
Failing to optimize the solution by checking each number for ugliness rather than using dynamic programming.
error
Incorrectly managing the pointers for 2, 3, and 5, which can result in missed ugly numbers.
error
Using brute force methods that don't leverage the state transition optimization, leading to inefficient solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the nth ugly number without using a heap, relying purely on dynamic programming.
arrow_right_alt
Optimize the solution for larger values of n, up to the maximum constraint.
arrow_right_alt
Extend the concept of ugly numbers to include other primes, such as 7, 11, etc.

help

常见问题

外企场景

继续练习

#996 平方数组的数目 #268 丢失的数字 #241 为运算表达式设计优先级