[LeetCode] 每日一题 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] <= 10^9
1 <= k <= 10^9
输入保证至少有一个满足
nums[i] >= k
的下标i
存在。
解题思路
今天这道每日一题应该是做过最简单的一道了
题目中提到,每次操作删除的是数组中的最小元素,但这并不会影响最终的解决方案。你可能会想是否需要反复判断哪些元素是最小的,是否要先处理最小的值等等,但稍微一想就会发现,无论是否是最小的,最后目标都是要通过删除小于 k
的元素来达成
因此,问题的关键点在于统计数组中小于 k
的元素数量,删除这些元素就能满足题目要求
代码实现
class Solution {
public int minOperations(int[] nums, int k) {
int ans = 0;
for (int num : nums) {
if (num < k) {
ans++;
}
}
return ans;
}
}
复杂度分析
时间复杂度:
O(n)
,其中n
是数组nums
的长度。我们只需要遍历一次数组,判断每个元素是否小于k
,因此时间复杂度为线性空间复杂度:
O(1)
,因为只用了常量空间来存储结果ans
,没有使用额外的空间
总结
这道题的关键在于简化思路。虽然题目提示每次操作是删除最小元素,但最终目标是去除所有小于 k
的元素。因此只需要统计并删除这些元素,代码实现非常直接,复杂度也相对较低
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。
License:
CC BY 4.0