LeetCode 题解工作台
丑数 III
丑数是可以被 a 或 b 或 c 整除的 正整数 。 给你四个整数： n 、 a 、 b 、 c ，请你设计一个算法来找出第 n 个丑数。 示例 1： 输入： n = 3, a = 2, b = 3, c = 5 输出： 4 解释： 丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... …
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
我们可以将题目转换为：找到最小的正整数 ，使得小于等于 的丑数个数恰好为 个。 对于一个正整数 ，能被 整除的数有 $\left\lfloor \frac{x}{a} \right\rfloor$ 个，能被 整除的数有 $\left\lfloor \frac{x}{b} \right\rfloor$ 个，能被 整除的数有 $\left\lfloor \frac{x}{c} \right\…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
丑数是可以被 a 或 b 或 c 整除的 正整数 。
给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。
示例 1：
输入：n = 3, a = 2, b = 3, c = 5 输出：4 解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
示例 2：
输入：n = 4, a = 2, b = 3, c = 4 输出：6 解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。
示例 3：
输入：n = 5, a = 2, b = 11, c = 13 输出：10 解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
提示：
1 <= n, a, b, c <= 1091 <= a * b * c <= 1018- 本题结果在
[1, 2 * 109]的范围内
解题思路
方法一：二分查找 + 容斥原理
我们可以将题目转换为：找到最小的正整数 ，使得小于等于 的丑数个数恰好为 个。
对于一个正整数 ，能被 整除的数有 个，能被 整除的数有 个，能被 整除的数有 个，能被 和 同时整除的数有 个，能被 和 同时整除的数有 个，能被 和 同时整除的数有 个，能被 , 和 同时整除的数有 个。根据容斥原理，小于等于 的丑数个数为：
我们可以使用二分查找的方法找到最小的正整数 ，使得小于等于 的丑数个数恰好为 个。
定义二分查找的左边界为 ，右边界为 ，其中 是题目给定的最大值。在二分查找的每一步中，我们找出中间数 ，如果小于等于 的丑数个数大于等于 ，那么说明最小的正整数 落在 区间内，否则落在 区间内。在二分查找的过程中，我们需要不断更新小于等于 的丑数个数，直到找到最小的正整数 。
时间复杂度 ，其中 。空间复杂度 。
class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
ab = lcm(a, b)
bc = lcm(b, c)
ac = lcm(a, c)
abc = lcm(a, b, c)
l, r = 1, 2 * 10**9
while l < r:
mid = (l + r) >> 1
if (
mid // a
+ mid // b
+ mid // c
- mid // ab
- mid // bc
- mid // ac
+ mid // abc
>= n
):
r = mid
else:
l = mid + 1
return l
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to quickly define a counting function using inclusion-exclusion.
- question_mark
Check if they correctly apply binary search over the answer space instead of sequence enumeration.
- question_mark
Watch for handling large integers and potential overflows when computing LCMs.
常见陷阱
外企场景- error
Forgetting to subtract overcounted numbers when applying inclusion-exclusion.
- error
Using brute-force iteration, which will time out for large n or large a, b, c values.
- error
Failing to handle integer overflow in LCM calculations, especially when a _b_ c is near 10^18.
进阶变体
外企场景- arrow_right_alt
Find nth ugly number for more than three divisors, requiring generalized inclusion-exclusion.
- arrow_right_alt
Compute the sum of the first n ugly numbers instead of just the nth.
- arrow_right_alt
Adapt the pattern to count numbers divisible by given primes in a dynamic range.