leetcode3066.超过阈值的最少操作数 II

univerexplorer2025-01-152025-01-20

3066. 超过阈值的最少操作数 II

中等（最小堆）

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一次操作中，你将执行：

选择 nums 中最小的两个整数 x 和 y 。
将 x 和 y 从 nums 中删除。
将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置。

注意， 只有当 nums 至少包含两个元素时，你才可以执行以上操作。

你需要使数组中的所有元素都大于或等于 k ，请你返回需要的最少操作次数。

示例 1：

输入： nums = [2,11,10,1,3], k = 10
输出： 2
解释： 第一次操作中，我们删除元素 1 和 2 ，然后添加 1 * 2 + 2 到 nums 中，nums 变为 [4, 11, 10, 3] 。
第二次操作中，我们删除元素 3 和 4 ，然后添加 3 * 2 + 4 到 nums 中，nums 变为 [10, 11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。

示例 2：

输入： nums = [1,1,2,4,9], k = 20
输出： 4
解释： 第一次操作后，nums 变为 [2, 4, 9, 3] 。
第二次操作后，nums 变为 [7, 4, 9] 。
第三次操作后，nums 变为 [15, 9] 。
第四次操作后，nums 变为 [33] 。
此时，数组中的所有元素都大于等于 20 ，所以我们停止操作。
使数组中所有元素都大于等于 20 需要的最少操作次数为 4 。

代码一：二分插入

超出时间限制 671 / 675 个通过的测试用例

def bisect(lst,k):
    l = 0
    r = len(lst)-1
    while l <= r:
        mid = (l+r) // 2
        if lst[mid] < k:
            l = mid + 1
            continue
        if lst[mid] > k:
            r = mid - 1
            continue
        return lst[:mid] + [k] + lst[mid:]
    return lst[:l] + [k] + lst[l:]
class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        nums.sort()
        if nums[0] >= k:
            return 0
        count = 0
        while len(nums) >= 2:
            count += 1
            a = nums.pop(0)
            b = nums.pop(0)
            nums = bisect(nums,min(a,b)*2+max(a,b)) 
            if nums[0] >= k:
                return count
        return count

思路：

首先将数组进行从小到大排序，如果最开始的数就大于等于 k ，说明不需要操作就满足要求，返回 0 。倘如不然，按要求删除前两个最小的数，再将 min(x, y) * 2 + max(x, y) 二分插入数组中，操作数加一。依次类推直到满足条件。

代码二：最小堆

每次选择最小的两个数操作，这可以用 最小堆 模拟。

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        heapify(nums)
        count = 0
        while True:
            a = heappop(nums)
            if a >= k:
                return count
            b = heappop(nums)
            heappush(nums,min(a,b)*2+max(a,b))
            count += 1

思路：

使用最小堆模拟可以很方便的插入数据，并且可以保证最前面的数是最小的。

代码三：最小堆优化

来自灵神

class Solution:
    def minOperations(self, h: List[int], k: int) -> int:
        heapify(h)
        ans = 0
        while h[0] < k:
            x = heappop(h)
            heapreplace(h, h[0] + x * 2)
            ans += 1
        return ans