最小化两个数组中的最大值
难度:
标签:
题目描述
We have two arrays arr1 and arr2 which are initially empty. You need to add positive integers to them such that they satisfy all the following conditions:
arr1containsuniqueCnt1distinct positive integers, each of which is not divisible bydivisor1.arr2containsuniqueCnt2distinct positive integers, each of which is not divisible bydivisor2.- No integer is present in both
arr1andarr2.
Given divisor1, divisor2, uniqueCnt1, and uniqueCnt2, return the minimum possible maximum integer that can be present in either array.
Example 1:
Input: divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3 Output: 4 Explanation: We can distribute the first 4 natural numbers into arr1 and arr2. arr1 = [1] and arr2 = [2,3,4]. We can see that both arrays satisfy all the conditions. Since the maximum value is 4, we return it.
Example 2:
Input: divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1 Output: 3 Explanation: Here arr1 = [1,2], and arr2 = [3] satisfy all conditions. Since the maximum value is 3, we return it.
Example 3:
Input: divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2 Output: 15 Explanation: Here, the final possible arrays can be arr1 = [1,3,5,7,9,11,13,15], and arr2 = [2,6]. It can be shown that it is not possible to obtain a lower maximum satisfying all conditions.
Constraints:
2 <= divisor1, divisor2 <= 1051 <= uniqueCnt1, uniqueCnt2 < 1092 <= uniqueCnt1 + uniqueCnt2 <= 109
代码结果
运行时间: 22 ms, 内存: 16.1 MB
/*
题目思路:
1. 使用Stream API来简化遍历和过滤的过程。
2. 从1开始生成无限的正整数流。
3. 对于每个数字，检查它是否可以添加到arr1或arr2中。
4. 使用Stream API的filter方法来过滤掉不符合条件的数字。
5. 使用limit方法来限制最终结果的大小。
6. 计算出两个数组中的最大值。
*/
import java.util.stream.IntStream;
public class Solution {
public int findMinimumMaxValue(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
int[] count = {0, 0};
return IntStream.iterate(1, i -> i + 1)
.filter(i -> (i % divisor1 != 0 && count[0] < uniqueCnt1) || (i % divisor2 != 0 && count[1] < uniqueCnt2))
.limit(uniqueCnt1 + uniqueCnt2)
.peek(i -> {
if (i % divisor1 != 0 && count[0] < uniqueCnt1) count[0]++;
else if (i % divisor2 != 0 && count[1] < uniqueCnt2) count[1]++;
})
.max()
.getAsInt();
}
}解释
方法:
此题的解题思路采用了二分查找的方法。首先定义一个有效性函数 valid，用于判断对于给定的最大值 mid，是否能够满足两个数组的条件。函数 valid 中，首先计算不能被 divisor1 和 divisor2 整除的正整数数量 va 和 vb。然后计算能同时被 divisor1 和 divisor2 整除的正整数数量 shared。最后判断 va 和 vb 是否分别大于等于 uniqueCnt1 和 uniqueCnt2，以及 va 和 vb 减去 shared 是否大于等于 uniqueCnt1 和 uniqueCnt2 的总和。二分查找的过程中，根据 valid 函数的返回值来调整搜索范围，最终找到满足条件的最小的最大值。
时间复杂度:
O(logN)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在二分查找的上限设置为2*(uniqueCnt1 + uniqueCnt2)+1，这个上限的计算方法有什么特别的依据吗？
▷🦆
在计算最小公倍数LCM时采用的是`divisor1*divisor2//gcd(divisor1, divisor2)`，这种方法在所有情况下都准确无误吗，特别是在较大的输入值时是否会有整数溢出的风险？
▷🦆
函数`valid`中`shared`的计算方法是`mid - mid//divisor1 - mid//divisor2 + mid//lcm`，这种计算方式的目的是什么，能否详细解释其逻辑？
▷