Easy

题目描述

给你一个下标从 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]。
此时，nums 的所有元素都大于或等于 10，所以我们可以停止操作。
可以证明 3 是使所有元素都大于或等于 10 所需的最少操作数。

示例 2：

输入：nums = [1,1,2,4,9], k = 1
输出：0
解释：数组的所有元素都大于或等于 1，所以我们不需要对 nums 应用任何操作。

示例 3：

输入：nums = [1,1,2,4,9], k = 9
输出：4
解释：只有 nums 的一个元素大于或等于 9，所以我们需要对 nums 应用操作 4 次。

提示：

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9
  • 输入保证存在至少一个下标 i 使得 nums[i] >= k

解题思路

解题思路

这是一道简单的数组问题，关键是理解题目要求。

核心观察： 每次操作都是删除数组中的最小元素，我们需要删除所有小于 k 的元素，使得剩余元素都 ≥ k。

分析过程：

  1. 既然每次都删除最小元素，那么最终会按照从小到大的顺序删除元素
  2. 我们需要删除所有小于 k 的元素
  3. 因此，答案就是数组中小于 k 的元素个数

多种解法思路：

  1. 直接计数法（推荐）：遍历数组，统计小于 k 的元素个数
  2. 排序法：排序后找到第一个 ≥ k 的位置
  3. 模拟法：真正模拟删除过程（过于复杂，不推荐）

推荐解法：直接计数法

  • 时间复杂度低
  • 空间复杂度最优
  • 代码简洁易懂

由于题目保证至少有一个元素 ≥ k，所以不需要处理边界情况。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int count = 0;
        for (int num : nums) {
            if (num < k) {
                count++;
            }
        }
        return count;
    }
};

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return sum(1 for num in nums if num < k)

public class Solution {
    public int MinOperations(int[] nums, int k) {
        int count = 0;
        foreach (int num in nums) {
            if (num < k) {
                count++;
            }
        }
        return count;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperations = function(nums, k) {
    let count = 0;
    for (let num of nums) {
        if (num < k) {
            count++;
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)需要遍历整个数组一次
空间复杂度O(1)只使用常数级别的额外空间

相关题目