文章

[LeetCode] 每日一题 3065. 超过阈值的最少操作数 I

题目链接

https://leetcode.cn/problems/minimum-operations-to-exceed-threshold-value-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