最小化两个数组中的最大值

难度: 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 ，所以返回 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 <= 10⁵
1 <= uniqueCnt1, uniqueCnt2 < 10⁹
2 <= uniqueCnt1 + uniqueCnt2 <= 10⁹

Submission

运行时间: 22 ms

内存: 16.1 MB

class Solution:
    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
        #小于等于mid的正整数分配给两个数组是否能将两个数组填满
        # 不能被d1整除的数量: va = mid - mid//d1
        # 不能被d2整除的数量: vb = mid - mid//d2
        # 能被d1且能被d2整除的数: v = lcm(d1,d2)Leatest Common Multiple(LCM) 同时被a和b整除的最小倍数 [最小公倍数=两整数的乘积÷最大公约数]
        # 辗转相除法：已知a,b,c为正整数，若a除以b余c，则GCD（a,b）=GCD (b,c)。
        # cnt1: va-v, cnt2: vb-v

        mn = 0
        mx = 2*(uniqueCnt1 + uniqueCnt2)+1

        def gcd(a:int, b:int) -> int:
            if a < b:
                return gcd(b, a)
            else:
                if a%b == 0:
                    return b
                return gcd(b, a%b)
            

        def valid(mid:int)->bool:
            va = mid - mid//divisor1
            vb = mid - mid//divisor2
            if va < uniqueCnt1 or vb < uniqueCnt2:
                return False
            lcm = divisor1*divisor2//gcd(divisor1,divisor2)
            shared = mid- mid//divisor1 -mid//divisor2 + mid//lcm
            return va >= uniqueCnt1 and vb >= uniqueCnt2 and va+vb-shared >= uniqueCnt1+uniqueCnt2        

        while mn+1<mx:
            mid = (mn+mx)//2
            if valid(mid):
                mx = mid
            else:
                mn = mid
        return mx

Explain

此题的解题思路采用了二分查找的方法。首先定义一个有效性函数 valid，用于判断对于给定的最大值 mid，是否能够满足两个数组的条件。函数 valid 中，首先计算不能被 divisor1 和 divisor2 整除的正整数数量 va 和 vb。然后计算能同时被 divisor1 和 divisor2 整除的正整数数量 shared。最后判断 va 和 vb 是否分别大于等于 uniqueCnt1 和 uniqueCnt2，以及 va 和 vb 减去 shared 是否大于等于 uniqueCnt1 和 uniqueCnt2 的总和。二分查找的过程中，根据 valid 函数的返回值来调整搜索范围，最终找到满足条件的最小的最大值。

时间复杂度: O(logN)

空间复杂度: O(1)

class Solution:
    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
        mn = 0
        mx = 2*(uniqueCnt1 + uniqueCnt2)+1

        def gcd(a:int, b:int) -> int:
            if a < b:
                return gcd(b, a)
            else:
                if a%b == 0:
                    return b
                return gcd(b, a%b)
            

        def valid(mid:int)->bool:
            va = mid - mid//divisor1
            vb = mid - mid//divisor2
            if va < uniqueCnt1 or vb < uniqueCnt2:
                return False
            lcm = divisor1*divisor2//gcd(divisor1,divisor2)
            shared = mid- mid//divisor1 -mid//divisor2 + mid//lcm
            return va >= uniqueCnt1 and vb >= uniqueCnt2 and va+vb-shared >= uniqueCnt1+uniqueCnt2        

        while mn+1<mx:
            mid = (mn+mx)//2
            if valid(mid):
                mx = mid
            else:
                mn = mid
        return mx

Explore

这个上限的设置是基于保守估计的考虑。考虑到问题中要求的是数组中不能被 divisor1 和 divisor2 整除的最小最大元素数量，最坏情况下，每个 divisor 可能分别占据一个数，剩余的数都是不可整除的。因此，为了保证有足够的数来满足 uniqueCnt1 和 uniqueCnt2 的需求，我们可以估计数值至少需要是 uniqueCnt1 和 uniqueCnt2 两倍的总和，再加一以保证可以覆盖所有可能的边界情况。这是一个保守的估计，用以确保在最坏的情形下，我们仍有足够的数值范围来进行搜索。

该方法在理论上是正确的，因为两个数的乘积除以它们的最大公约数确实是它们的最小公倍数（LCM）。然而，在实际应用中，当 divisor1 和 divisor2 非常大时，直接计算 `divisor1*divisor2` 可能会导致整数溢出，尤其是在某些编程语言中，这可能会导致运算结果不准确。为了避免这种情况，可以先除以 gcd，再与另一个除数相乘，即 `lcm = (divisor1 // gcd(divisor1, divisor2)) * divisor2`。这样做可以减少乘法运算中的数值大小，从而减少溢出的风险。

这种计算方法基于容斥原理。函数中的 `shared` 是用来计算同时被 divisor1 和 divisor2 整除的数的数量。首先，`mid // divisor1` 给出了小于或等于 mid 的数中能被 divisor1 整除的数的数量，`mid // divisor2` 给出了能被 divisor2 整除的数量。这两个集合相加时，同时被 divisor1 和 divisor2 整除的数被重复计算了一次，因此需要减去这部分的重复计数，即 `mid // lcm`，这里 lcm 是 divisor1 和 divisor2 的最小公倍数。因此，`mid - mid//divisor1 - mid//divisor2 + mid//lcm` 正确计算了不被 divisor1 或 divisor2 整除的数的数量。