LeetCode 题解工作台
最小化两个数组中的最大值
给你两个数组 arr1 和 arr2 ，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件： arr1 包含 uniqueCnt1 个 互不相同 的正整数，每个整数都 不能 被 divisor1 整除 。 arr2 包含 uniqueCnt2 个 互不相同 的正整数，每个整数都 不能 …
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
class Solution: def minimizeSet(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你两个数组 arr1 和 arr2 ，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件：
arr1包含uniqueCnt1个 互不相同 的正整数，每个整数都 不能 被divisor1整除 。arr2包含uniqueCnt2个 互不相同 的正整数，每个整数都 不能 被divisor2整除 。arr1和arr2中的元素 互不相同 。
给你 divisor1 ，divisor2 ，uniqueCnt1 和 uniqueCnt2 ，请你返回两个数组中 最大元素 的 最小值 。
示例 1：
输入：divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3 输出：4 解释： 我们可以把前 4 个自然数划分到 arr1 和 arr2 中。 arr1 = [1] 和 arr2 = [2,3,4] 。 可以看出两个数组都满足条件。 最大值是 4 ，所以返回 4 。
示例 2：
输入：divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1 输出：3 解释： arr1 = [1,2] 和 arr2 = [3] 满足所有条件。 最大值是 3 ，所以返回 3 。
示例 3：
输入：divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2 输出：15 解释： 最终数组为 arr1 = [1,3,5,7,9,11,13,15] 和 arr2 = [2,6] 。 上述方案是满足所有条件的最优解。
提示：
2 <= divisor1, divisor2 <= 1051 <= uniqueCnt1, uniqueCnt2 < 1092 <= uniqueCnt1 + uniqueCnt2 <= 109
解题思路
方法一
class Solution:
def minimizeSet(
self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int
) -> int:
def f(x):
cnt1 = x // divisor1 * (divisor1 - 1) + x % divisor1
cnt2 = x // divisor2 * (divisor2 - 1) + x % divisor2
cnt = x // divisor * (divisor - 1) + x % divisor
return (
cnt1 >= uniqueCnt1
and cnt2 >= uniqueCnt2
and cnt >= uniqueCnt1 + uniqueCnt2
)
divisor = lcm(divisor1, divisor2)
return bisect_left(range(10**10), True, key=f)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the efficiency of the binary search and array distribution steps. The binary search reduces the search space, while the array calculation checks each candidate efficiently. Space complexity is dependent on the storage required for maintaining intermediate states during the search process. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates strong understanding of binary search and optimization techniques.
- question_mark
Effective handling of divisor-related number theory, ensuring unique counts are respected.
- question_mark
Clear explanation of how to balance the distribution between the two arrays while minimizing the maximum.
常见陷阱
外企场景- error
Misunderstanding the binary search boundaries could lead to unnecessary computation.
- error
Incorrectly distributing the numbers between the arrays, causing an invalid configuration.
- error
Failing to optimize the approach by prematurely narrowing the search space or miscalculating unique counts.
进阶变体
外企场景- arrow_right_alt
Change the divisors and unique counts to test different configurations.
- arrow_right_alt
Increase the range of possible numbers to test performance with larger constraints.
- arrow_right_alt
Modify the approach to handle more than two arrays, adding complexity to the distribution problem.