使数字变为非正数的最小操作次数

Submission

运行时间: 460 ms

内存: 30.3 MB

class Solution:
    def minOperations(self, nums: List[int], x: int, y: int) -> int:
        def check(k):
            ans = 0
            for a in nums:
                a -= k*y
                if a>0:
                    ans += (a-1)//(x-y)+1
                    if ans>k:
                        return False
            return True

        return bisect_left(range(max(nums)//y+1),True,key=check)

Explain

此题解使用了二分查找和贪心算法的结合。首先，定义一个内部函数 check(k)，该函数用于检查是否可以通过至多 k 次操作将所有数字减至不大于 0。在每次操作中，可以选择将任一数字减去 y 或 x-y（如果 x>y）。函数 check 遍历每个数字，首先将数字减去 k*y，然后根据剩余的正数部分计算需要多少次 x-y 的减法操作，如果总操作次数超过 k，则返回 False。主函数中，使用二分查找确定最小的满足条件的 k 值，即查找第一个使 check 函数返回 True 的 k 值。

时间复杂度: O(n log(max(nums)/y))

空间复杂度: O(1)

class Solution:
    def minOperations(self, nums: List[int], x: int, y: int) -> int:
        # 检查是否可通过至多 k 次操作使所有数字非正
        def check(k):
            ans = 0
            for a in nums:
                a -= k * y  # 对每个数减去 k 次 y
                if a > 0:
                    # 如果仍为正数，则计算减去 x-y 需要的次数
                    ans += (a - 1) // (x - y) + 1
                    # 如果操作次数超过 k，则返回 False
                    if ans > k:
                        return False
            return True

        # 二分查找最小的 k 值
        return bisect_left(range(max(nums) // y + 1), True, key=check)

Explore

选择`max(nums) // y + 1`作为搜索范围的上界是因为在最极端的情况下，即每次操作只减去`y`而不使用`x-y`的情况下，要使最大的数字变为非正数至少需要`max(nums) // y`次操作。加1是因为二分查找的范围需要覆盖可能的边界情况。理论上，这是一个保守的估计，实际上可能存在更小的`k`值，因为在一些情况下使用`x-y`操作可以更高效地减少数字，从而减少操作次数。这是初步设定的上界，二分查找将在这个范围内找到实际的最小`k`。

在`check`函数中，只有当数字减去`k*y`后仍然大于0时，才需要进一步考虑使用`x-y`操作，因为如果数字已经非正，则不需要进一步操作。如果`x-y`为负数，实际上这种情况在题目设定中不应存在，因为这会使问题变得无意义（即无法通过减去一个负数使数字变小）。通常，我们假定`x > y`以确保`x-y`为正，从而使得每次操作都有效地减少数字。

使用`(a - 1) // (x - y) + 1`的计算方式是为了处理任何正整数`a`的情况，确保能够正确计算出将`a`减至0或以下所需的最小操作次数。当`a`正好是`x-y`的倍数时，这种计算方式依然有效。例如，如果`a = (x-y) * 2`，那么`(a - 1) // (x - y) + 1`计算结果将是3，但由于我们是从`a-1`开始计算的，所以实际上我们只需要2次操作，这正符合预期的结果。

如果`x`小于`y`，题解中的逻辑将不适用，因为在这种情况下，`x-y`将是负数，这意味着操作会增加数字而不是减少，与题目要求相矛盾。题解假设`x > y`以确保每次操作都能有效地减少数值。如果`x < y`，则需要重新考虑问题的设定和解决方案。