【拒绝算法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;
    }
};