[leetcode/lintcode 题解] 阿里算法面试真题:丑数 II · Ugly Number II

简介: [leetcode/lintcode 题解] 阿里算法面试真题:丑数 II · Ugly Number II

描述
设计一个算法,找出只含素因子2,3,5 的第 n 小的数。
符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12...:

我们可以认为 1 也是一个丑数。

在线评测地址:领扣题库官网

样例1
输入:9
输出:10
AI 代码解读
样例2
输入:1
输出:1
AI 代码解读

解题思路1:最小堆

  • 很容易想到的方法是:从1起检验每个数是否为丑数,直到找到n个丑数为止。但是随着n的增大,绝大部分数字都不是丑数,我们枚举的效率非常低。因此,换个角度思考,如果我们只生成丑数,且生成n个,这道题就迎刃而解。
  • 不难发现生成丑数的规律:如果已知丑数ugly,那么ugly 2,ugly 3和ugly * 5也都是丑数。
  • 既然求第n小的丑数,可以采用最小堆来解决。每次弹出堆中最小的丑数,然后检查它分别乘以2、3和 5后的数是否生成过,如果是第一次生成,那么就放入堆中。第n个弹出的数即为第n小的丑数。

算法流程

  • 创建最小堆heap,哈希表 seen和质因数列表factors = [2, 3, 5]。heap用于存储已生成的丑数,弹出最小值;seen用于标记堆中出现过的元素,避免重复入堆。
  • 初始化将1入堆,并添加到seen。
  • 重复以下步骤n次: 弹出堆中最小的数字 curr_ugly。 对于factors中每个因数f,生成新的丑数new_ugly。若new_ugly不在seen中,则将其添加到heap中并更新seen。
  • curr_ugly即为第n小的丑数,返回。

复杂度分析

  • 时间复杂度:O(nlog(n))O(nlog(n))。弹出每个最小值时,时间复杂度都为堆的高度,因此时间复杂度为O(nlog(n))O(nlog(n))。
  • 空间复杂度:O(n)O(n)。遍历n个丑数,并将每个丑数乘以2、3和5的结果存入堆中。堆和哈希表的元素个数都不会超过n * 3。

代码
import heapq

class Solution:
    """
    @param n: An integer
    @return: return a  integer as description.
    """
    def nthUglyNumber(self, n):
        heap = []
        heapq.heappush(heap, 1)

        seen = set()
        seen.add(1)

        factors = [2, 3, 5]

        curr_ugly = 1
        
        for _ in range(n):
            # 每次弹出当前最小丑数
            curr_ugly = heapq.heappop(heap)
            # 生成新的丑数
            for f in factors:
                new_ugly = curr_ugly * f
                if new_ugly not in seen:
                    seen.add(new_ugly)
                    heapq.heappush(heap, new_ugly)
        return curr_ugly
AI 代码解读

解题思路2:动态规划

  • 在最小堆方法中,我们的思路是把当前丑数能生成的丑数都加入到堆中,然后再弹出最小值。如果我们能知道下一个最小的丑数,每次只生成最小的那个,就可以节省最小值查询的时间消耗。
  • 采用动态规划的方法,用一个有序数组dp记录前n个丑数。三个指针l2,l3和l5指向dp中的元素,最小的丑数只可能出现在dp[l2]的2倍、dp[l3]的3倍和dp[l5]的5倍三者中间。通过移动三个指针,就能保证生成的丑数是有序的。

算法流程

  • 初始化数组dp和三个指针l2、l3和l5。dp[0] = 1,表示最小的丑数为1。三个指针都指向dp[0]。
  • 重复以下步骤n次,dp[i]表示第i + 1小的丑数:

    • 比较2 dp[l2], 3 dp[l3], 5 * dp[l5]三者大小,令dp[i]为其中的最小值。
    • 如果dp[i] == 2 * dp[l2],l2指针后移一位。
    • 如果dp[i] == 3 * dp[l3],l3指针后移一位。
    • 如果dp[i] == 2 * dp[l5],l5指针后移一位。
  • dp[n - 1]即为第n小的丑数,返回。

复杂度分析

  • 时间复杂度:O(n)O(n)。生成一个丑数只需常量时间,所以生成n个丑数需要O(n)O(n)。
  • 空间复杂度:O(n)O(n)。dp数组的长度为n。

代码
import heapq

class Solution:
    """
    @param n: An integer
    @return: return a  integer as description.
    """
    def nthUglyNumber(self, n):
        dp = [0] * n
        dp[0] = 1
        l2, l3, l5 = 0, 0, 0
        for i in range(1, n):
            # 生成第i+1小的丑数
            dp[i] = min(2 * dp[l2], 3 * dp[l3], 5 * dp[l5])
            if dp[i] == 2 * dp[l2]:
                l2 += 1
            if dp[i] == 3 * dp[l3]:
                l3 += 1
            if dp[i] == 5 * dp[l5]:
                l5 += 1
        return dp[n - 1]
AI 代码解读

更多题解参考:九章官网solution

目录
打赏
0
0
0
0
6
分享
相关文章
|
4月前
|
面试场景题:如何设计一个抢红包随机算法
本文详细解析了抢红包随机算法的设计与实现,涵盖三种解法:随机分配法、二倍均值法和线段切割法。随机分配法通过逐次随机分配金额确保总额不变,但易导致两极分化;二倍均值法优化了金额分布,使每次抢到的金额更均衡;线段切割法则将总金额视为线段,通过随机切割点生成子金额,手气最佳金额可能更高。代码示例清晰,结果对比直观,为面试中类似算法题提供了全面思路。
969 16
|
9月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
92 0
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
161 4
|
9月前
|
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
86 2
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
450 2
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
141 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
11月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
112 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
231 2

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问