超过阈值的最少操作数 II
难度:
标签:
题目描述
You are given a 0-indexed integer array nums, and an integer k.
In one operation, you will:
- Take the two smallest integers
xandyinnums. - Remove
xandyfromnums. - 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 * 1051 <= nums[i] <= 1091 <= k <= 109- 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.
代码结果
运行时间: 226 ms, 内存: 35.2 MB
/*
题目思路:
1. 使用Java Stream对数组进行排序。
2. 不断执行操作，选择最小的两个元素，将它们删除，并计算新元素加入数组。
3. 每次操作后重新插入新元素，并继续操作，直到数组中所有元素都大于或等于k。
4. 统计所需的操作次数。
*/
import java.util.Arrays;
import java.util.PriorityQueue;
public class Solution {
public int minOperations(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.stream(nums).boxed().toList());
int operations = 0;
while (pq.size() > 1 && pq.peek() < k) {
int x = pq.poll();
int y = pq.poll();
int newElement = x * 2 + y;
pq.offer(newElement);
operations++;
}
return operations;
}
}解释
方法:
这个题解的核心思路是使用贪心算法结合两个双端队列（deque）来高效地处理数组。首先，对输入数组nums进行排序，然后使用两个队列q1和q2。q1初始化为排序后的nums，q2用于存放每次操作产生的新元素。在每次操作中，选择q1和q2队头的最小的两个元素进行合并操作，并将结果存入q2。这个过程重复进行，直到所有元素都大于等于k。操作过程中，如果在任意步骤发现已选的任一元素大于等于k，则可以提前结束操作。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在选择最小的两个元素进行合并时，为什么使用两个队列而不是一个队列或其他数据结构？
▷🦆
当从两个队列q1和q2中选择元素时，为什么优先选择队列q1的元素？
▷🦆
如果在操作过程中q1已经为空，而q2包含了所有元素，这种情况下算法的效率如何？
▷