class Solution {
public:
int minOperations(vector<int>& nums, int k) {
}
};
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 * 1051 <= nums[i] <= 1091 <= k <= 109k 。原站题解
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