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

🟠 🔖 数组 模拟 堆（优先队列） 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a 0-indexed integer array nums, and an integer k.

In one operation, you will:

Take the two smallest integers x and y in nums.
Remove x and y from nums.
Add min(x, y) * 2 + max(x, y) anywhere in the array.

Note that you can only apply the described operation if nums contains at least two elements.

Return the minimum number of operations needed so that all elements of the array are greater than or equal to k.

Example 1:

Input: nums = [2,11,10,1,3], k = 10
Output: 2
Explanation: In the first operation, we remove elements 1 and 2, then add 1 * 2 + 2 to nums. nums becomes equal to [4, 11, 10, 3].
In the second operation, we remove elements 3 and 4, then add 3 * 2 + 4 to nums. nums becomes equal to [10, 11, 10].
At this stage, all the elements of nums are greater than or equal to 10 so we can stop.
It can be shown that 2 is the minimum number of operations needed so that all elements of the array are greater than or equal to 10.

Example 2:

Input: nums = [1,1,2,4,9], k = 20
Output: 4
Explanation: After one operation, nums becomes equal to [2, 4, 9, 3].
After two operations, nums becomes equal to [7, 4, 9].
After three operations, nums becomes equal to [15, 9].
After four operations, nums becomes equal to [33].
At this stage, all the elements of nums are greater than 20 so we can stop.
It can be shown that 4 is the minimum number of operations needed so that all elements of the array are greater than or equal to 20.

Constraints:

2 <= nums.length <= 2 * 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9
The input is generated such that an answer always exists. That is, there exists some sequence of operations after which all elements of the array are greater than or equal to k.

题目大意

给你一个下标从 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^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9
输入保证答案一定存在，也就是说一定存在一个操作序列使数组中所有元素都大于等于 k 。

解题思路

使用最小堆维护最小值
- 题目要求将数组元素进行合并操作，直到最小元素大于等于 k，每次合并需要取出最小的两个数并进行计算，因此适合使用 最小堆 (MinHeap) 进行管理。
构建最小堆
- 使用最小堆存储数组 nums，这样每次可以快速找到当前最小的两个数。
执行合并操作
- 每次从堆中取出两个最小元素 first 和 second，计算合并后的值 first * 2 + second。
- 将新的值插入堆中，并增加操作次数 count++。
- 直到堆顶元素 heap.top() 大于等于 k 时停止。

复杂度分析

时间复杂度：O(n log n)，
- 构造最小堆需要 O(n) 时间。
- 每次合并操作涉及 heap.pop()（O(log n)）和 heap.insert()（O(log n)），最多执行 n-1 次，因此总时间复杂度为 O(n log n)。
空间复杂度：O(n)，额外使用了最小堆存储 n 个元素。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperations = function (nums, k) {
	let count = 0;
	let heap = new MinHeap(nums);
	while (heap.top() < k) {
		const first = heap.pop();
		const second = heap.pop();
		heap.insert(first * 2 + second);
		count++;
	}
	return count;
};

// 最小堆
class MinHeap {
	constructor(arr = []) {
		this.heap = arr;
		for (let i = ((this.heap.length / 2) | 0) - 1; i >= 0; i--) {
			this.heapifyDown(i);
		}
	}
	insert(num) {
		this.heap.push(num);
		this.heapifyUp(this.heap.length - 1);
	}
	pop() {
		if (this.heap.length == 0) return null;
		const top = this.heap[0],
			last = this.heap.pop();
		if (this.heap.length > 0) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}
	top() {
		return this.heap[0];
	}
	size() {
		return this.heap.length;
	}
	heapifyDown(i) {
		const left = i * 2 + 1,
			right = i * 2 + 2;
		let min = i;
		if (left < this.heap.length && this.heap[left] < this.heap[min]) {
			min = left;
		}
		if (right < this.heap.length && this.heap[right] < this.heap[min]) {
			min = right;
		}
		if (min !== i) {
			[this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
			this.heapifyDown(min);
		}
	}
	heapifyUp(i) {
		while (i) {
			const parent = ((i - 1) / 2) | 0;
			if (this.heap[i] < this.heap[parent]) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}
}

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

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

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

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

题目

题目大意

解题思路

复杂度分析

代码

相关题目