超过阈值的最少操作数 II

100232. 超过阈值的最少操作数 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 。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minOperations(vector<int>& nums, int k) { } };

rust 解法, 执行用时: 44 ms, 内存消耗: 5.3 MB, 提交时间: 2025-01-15 00:27:14

use std::collections::BinaryHeap;

impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        let mut h = BinaryHeap::new();
        for x in nums {
            h.push(-x as i64); // 取负号变成最小堆
        }

        let mut ans = 0;
        while -h.peek().unwrap() < k as i64 {
            let x = h.pop().unwrap();
            let y = h.pop().unwrap();
            h.push(x * 2 + y);
            ans += 1;
        }
        ans
    }
}

javascript 解法, 执行用时: 717 ms, 内存消耗: 96.7 MB, 提交时间: 2025-01-15 00:26:48

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperations = function(nums, k) {
    const pq = new MinPriorityQueue(); // datastructures-js/priority-queue@5.4.0
    for (const x of nums) {
        pq.enqueue(x);
    }

    let ans = 0;
    while (pq.front().element < k) {
        const x = pq.dequeue().element;
        const y = pq.dequeue().element;
        pq.enqueue(x * 2 + y);
        ans++;
    }
    return ans;
};

cpp 解法, 执行用时: 112 ms, 内存消耗: 96.9 MB, 提交时间: 2025-01-15 00:26:33

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        priority_queue<long long, vector<long long>, greater<>> pq;
        for (int x : nums) {
            pq.push((long long) x);
        }

        int ans = 0;
        while (pq.top() < k) {
            long long x = pq.top(); pq.pop();
            long long y = pq.top(); pq.pop();
            pq.push(x * 2 + y);
            ans++;
        }
        return ans;
    }
};

php 解法, 执行用时: 353 ms, 内存消耗: 30.3 MB, 提交时间: 2024-03-04 10:08:16

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function minOperations($nums, $k) {
        $ans = 0;
        $h = new \SplMinHeap();
        foreach ( $nums as $num ) {
            $h->insert($num);
        }
        
        while ( $h->current() < $k ) {
            $x = $h->extract();
            $y = $h->extract();
            $h->insert($x * 2 + $y);
            $ans++;
        }
        return $ans;
    }
}

golang 解法, 执行用时: 186 ms, 内存消耗: 10.8 MB, 提交时间: 2024-03-04 09:59:56

func minOperations(nums []int, k int) (ans int) {
	h := &hp{nums}
	heap.Init(h)
	for h.IntSlice[0] < k {
		x := heap.Pop(h).(int)
		h.IntSlice[0] += x * 2
		heap.Fix(h, 0)
		ans++
	}
	return
}

type hp struct{ sort.IntSlice }
func (hp) Push(any)    {}
func (h *hp) Pop() any { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

java 解法, 执行用时: 158 ms, 内存消耗: 69.1 MB, 提交时间: 2024-03-04 09:59:41

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

python3 解法, 执行用时: 241 ms, 内存消耗: 33.9 MB, 提交时间: 2024-03-04 09:58:32

# 最小堆模拟
class Solution:
    def minOperations(self, h: List[int], k: int) -> int:
        from heapq import heapify, heappop, heapreplace
        ans = 0
        heapify(h)
        while h[0] < k:
            x = heappop(h)
            heapreplace(h, x * 2 + h[0])
            ans += 1
        return ans

上一题

下一题

详情