【拒绝算法PUA】3065. 超过阈值的最少操作数 I

系列文章目录

【拒绝算法PUA】0x00-位运算
【拒绝算法PUA】0x01- 区间比较技巧
【拒绝算法PUA】0x02- 区间合并技巧
【拒绝算法PUA】0x03 - LeetCode 排序类型刷题
【拒绝算法PUA】LeetCode每日一题系列刷题汇总-2025年持续刷新中

C++刷题技巧总结：
[温习C/C++]0x04 刷题基础编码技巧

---

---

LeetCode 3065. 超过阈值的最少操作数 I

链接

3065. 超过阈值的最少操作数 I

题目

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。一次操作中，你可以删除 nums 中的最小元素。你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。示例 1：输入：nums = [2,11,10,1,3], k = 10
输出：3
解释：第一次操作后，nums 变为 [2, 11, 10, 3] 。
第二次操作后，nums 变为 [11, 10, 3] 。
第三次操作后，nums 变为 [11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 3 。
示例 2：输入：nums = [1,1,2,4,9], k = 1
输出：0
解释：数组中的所有元素都大于等于 1 ，所以不需要对 nums 做任何操作。
示例 3：输入：nums = [1,1,2,4,9], k = 9
输出：4
解释：nums 中只有一个元素大于等于 9 ，所以需要执行 4 次操作。提示：1 <= nums.length <= 50
1 <= nums[i] <= 109
1 <= k <= 109
输入保证至少有一个满足 nums[i] >= k 的下标 i 存在。

解题方法1 (排序，然后for循环判断)

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
public:int minOperations(vector<int>& nums, int k) {vector<int> copy(nums.begin(), nums.end());std::sort(copy.begin(), copy.end(), std::less<int>());int ans = 0;int size = nums.size();for (int i =0; i < size; i++) {if (copy[i] >= k) {ans = i;break;}}return ans;}
};int main(int argc, char **argv) {vector<int> vec = {2, 11, 10, 1, 3};int k = 10;Solution obj;int ret = obj.minOperations(vec, k);cout << ret << endl;return 0;
}

输出：

3

解题方法2(利用小顶堆优化)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>using namespace std;class Solution {
public:struct cmp {bool operator()(int a, int b) {return a > b; // 小顶堆}};int minOperations(vector<int>& nums, int k) {int ans = 0;priority_queue<int, vector<int>, cmp> pq(nums.begin(), nums.end());while (!pq.empty() && pq.top() < k) {pq.pop();}ans = nums.size() - pq.size();return ans;}
};