Medium

题目描述

我们有两个初始为空的数组 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，我们返回它。

示例 2：

输入：divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
输出：3
解释：
这里 arr1 = [1,2]，arr2 = [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 <= 10^5
  • 1 <= uniqueCnt1, uniqueCnt2 < 10^9
  • 2 <= uniqueCnt1 + uniqueCnt2 <= 10^9

解题思路

这道题的核心思想是使用二分搜索来找到满足条件的最小的最大值。

首先我们需要理解题目要求：

  1. arr1 需要 uniqueCnt1 个不被 divisor1 整除的数
  2. arr2 需要 uniqueCnt2 个不被 divisor2 整除的数
  3. 两个数组不能有重复元素

关键洞察是，对于给定的上界 mid，我们需要检查是否能用 1 到 mid 的数字满足所有条件。

检查函数的逻辑：

  • 计算 1 到 mid 中不被 divisor1 整除的数的个数（可以放入 arr1 或共用）
  • 计算 1 到 mid 中不被 divisor2 整除的数的个数（可以放入 arr2 或共用）
  • 计算既不被 divisor1 也不被 divisor2 整除的数的个数（可以放入任一数组）

使用最大公约数（GCD）和最小公倍数（LCM）来计算被两个除数同时整除的数的个数。

贪心策略：优先使用只能放入特定数组的数字，然后使用可以放入任一数组的数字来补足剩余需求。

二分搜索的范围从 1 到 uniqueCnt1 + uniqueCnt2（理论最大值）。

代码实现

class Solution {
public:
    int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        long long left = 1, right = (long long)uniqueCnt1 + uniqueCnt2;
        long long lcm = (long long)divisor1 / __gcd(divisor1, divisor2) * divisor2;
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            
            // Count numbers not divisible by divisor1 (can go to arr1 or shared)
            long long notDiv1 = mid - mid / divisor1;
            // Count numbers not divisible by divisor2 (can go to arr2 or shared)
            long long notDiv2 = mid - mid / divisor2;
            // Count numbers not divisible by either (can go to either array)
            long long notDivBoth = mid - mid / divisor1 - mid / divisor2 + mid / lcm;
            
            // Check if we can satisfy the requirements
            long long need1 = max(0LL, (long long)uniqueCnt1 - notDivBoth);
            long long need2 = max(0LL, (long long)uniqueCnt2 - notDivBoth);
            
            if (need1 <= notDiv1 - notDivBoth && 
                need2 <= notDiv2 - notDivBoth && 
                need1 + need2 <= notDiv1 + notDiv2 - notDivBoth) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return (int)left;
    }
};

class Solution:
    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
        import math
        
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        lcm = divisor1 * divisor2 // gcd(divisor1, divisor2)
        
        left, right = 1, uniqueCnt1 + uniqueCnt2
        
        while left < right:
            mid = (left + right) // 2
            
            # Count numbers not divisible by divisor1
            not_div1 = mid - mid // divisor1
            # Count numbers not divisible by divisor2
            not_div2 = mid - mid // divisor2
            # Count numbers not divisible by either
            not_div_both = mid - mid // divisor1 - mid // divisor2 + mid // lcm
            
            # Check if we can satisfy requirements
            need1 = max(0, uniqueCnt1 - not_div_both)
            need2 = max(0, uniqueCnt2 - not_div_both)
            
            if (need1 <= not_div1 - not_div_both and 
                need2 <= not_div2 - not_div_both and 
                need1 + need2 <= not_div1 + not_div2 - not_div_both):
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public int MinimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        long left = 1, right = (long)uniqueCnt1 + uniqueCnt2;
        long lcm = (long)divisor1 / Gcd(divisor1, divisor2) * divisor2;
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            
            long notDiv1 = mid - mid / divisor1;
            long notDiv2 = mid - mid / divisor2;
            long notDivBoth = mid - mid / divisor1 - mid / divisor2 + mid / lcm;
            
            long need1 = Math.Max(0L, (long)uniqueCnt1 - notDivBoth);
            long need2 = Math.Max(0L, (long)uniqueCnt2 - notDivBoth);
            
            if (need1 <= notDiv1 - notDivBoth && 
                need2 <= notDiv2 - notDivBoth && 
                need1 + need2 <= notDiv1 + notDiv2 - notDivBoth) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return (int)left;
    }
    
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var minimizeSet = function(divisor1, divisor2, uniqueCnt1, uniqueCnt2) {
    function gcd(a, b) {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    }
    
    const lcm = Math.floor(divisor1 / gcd(divisor1, divisor2)) * divisor2;
    let left = 1, right = uniqueCnt1 + uniqueCnt2;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        const notDiv1 = mid - Math.floor(mid / divisor1);
        const notDiv2 = mid - Math.floor(mid / divisor2);
        const notDivBoth = mid - Math.floor(mid / divisor1) - Math.floor(mid / divisor2) + Math.floor(mid / lcm);
        
        const need1 = Math.max(0, uniqueCnt1 - notDivBoth);
        const need2 = Math.max(0, uniqueCnt2 - notDivBoth);
        
        if (need1 <= notDiv1 - notDivBoth && 
            need2 <= notDiv2 - notDivBoth && 
            need1 + need2 <= notDiv1 + notDiv2 - notDivBoth) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(log(uniqueCnt1 + uniqueCnt2))
空间复杂度O(1)