当前位置：首页 > article >正文

LeetCode 3066.超过阈值的最少操作数 II：模拟 - 原地建堆O(1)空间 / 优先队列O(n)空间

article 2025/1/16 17:17:44

【LetMeFly】3066.超过阈值的最少操作数 II：模拟 - 原地建堆O(1)空间 / 优先队列O(n)空间

力扣题目链接：https://leetcode.cn/problems/minimum-operations-to-exceed-threshold-value-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 。

提示：

2 <= nums.length <= 2 * 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹
输入保证答案一定存在，也就是说一定存在一个操作序列使数组中所有元素都大于等于 k 。

解题方法：小根堆

这道题说明了让你模拟，那咱就模拟。

使用小根堆（堆顶元素最小）。每次从堆中取出两个元素，并将计算结果放回堆中。

这样就保证了每次取出的元素都是当前最小值，直到堆顶元素 $\geq k$ 停止。

时间复杂度 $O(n\log n)$ ：原地建堆时间复杂度 $O (n)$ ，优先队列（额外建堆）时间复杂度 $O(n\log n)$ ；单次操作时间复杂度 $O(\log n)$ ，操作次数不超过 $n$ 次
空间复杂度：原地建堆 $O (1)$ ，优先队列（额外建堆） $O (n)$

AC代码

C++ - 原地建堆

/*
 * @Author: LetMeFly
 * @Date: 2025-01-15 13:38:52
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-15 13:58:45
 */
class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int ans = 0;
        make_heap(nums.begin(), nums.end(), greater<>());
        while (nums[0] < k) {
            int x = nums[0];
            pop_heap(nums.begin(), nums.end() - ans, greater<>());
            int y = nums[0];
            pop_heap(nums.begin(), nums.end() - (ans + 1), greater<>());
            nums[nums.size() - ans - 2] = min((unsigned)k, (unsigned)x + (unsigned)y + (unsigned)min(x, y));
            push_heap(nums.begin(), nums.end() - (ans + 1), greater<>());
            ans++;
        }
        return ans;
    }
};

执行用时分布120ms击败49.31%；
消耗内存分布83.55MB击败100.00%。

Python - 原地建堆

'''
Author: LetMeFly
Date: 2025-01-15 14:02:08
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-15 14:12:18
'''
from typing import List
import heapq

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        ans = 0
        heapq.heapify(nums)
        while nums[0] < k:
            x = nums[0]
            heapq.heappop(nums)
            y = nums[0]
            heapq.heappop(nums)
            heapq.heappush(nums, 2 * min(x, y) + max(x, y))
            ans += 1
        return ans

if __name__ == '__main__':
    sol = Solution()
    print(sol.minOperations([2, 11, 10, 1, 3], 10))

Java - 优先队列

/*
 * @Author: LetMeFly
 * @Date: 2025-01-15 14:22:12
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-15 14:30:40
 */
import java.util.PriorityQueue;

class Solution {
    public int minOperations(int[] nums, int k) {
        int ans = 0;
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for (int t : nums) {
            pq.add((long)t);
        }
        while (pq.peek() < k) {
            long x = pq.remove(), y = pq.remove();
            pq.add(Math.min(x, y) * 2 + Math.max(x, y));
            ans++;
        }
        return ans;
    }
}

Go - 优先队列

/*
 * @Author: LetMeFly
 * @Date: 2025-01-15 14:37:30
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-15 14:53:17
 */
package main

import "container/heap"

func minOperations(nums []int, k int) (ans int) {
    pq := make(heap_MOETV2, 0)
    heap.Init(&pq)
    for _, n := range nums {
        heap.Push(&pq, n)
    }
    for ; pq[0] < k; ans++ {
        x, y := heap.Pop(&pq).(int), heap.Pop(&pq).(int)
        heap.Push(&pq, x + x + y)
    }
    return
}


type heap_MOETV2 []int

func (h heap_MOETV2) Len() int { return len(h) }
func (h heap_MOETV2) Less(i, j int) bool { return h[i] < h[j] }
func (h heap_MOETV2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *heap_MOETV2) Push(a interface{}) { *h = append(*h, a.(int)) }
func (h *heap_MOETV2) Pop() interface{} { temp := *h; ans := temp[len(temp) - 1]; (*h) = temp[0:len(temp) - 1]; return ans }