超过阈值的最少操作数 I

难度: 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] 。
此时，数组中的所有元素都大于等于 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⁹
1 <= k <= 10⁹
输入保证至少有一个满足 nums[i] >= k 的下标 i 存在。

Submission

运行时间: 23 ms

内存: 16.0 MB

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        nums.sort()
        n=len(nums)
        for i in range(n):
            if nums[i]>=k:
                return i

Explain

首先对数组进行排序，使得所有元素按照升序排列。排序后，数组中小于 k 的元素都会出现在数组的前面，大于等于 k 的元素会出现在后面。通过遍历排序后的数组，找到第一个大于等于 k 的元素的位置，该位置的索引即是需要移除的元素数量，因为所有小于 k 的元素都需要被移除以满足题目要求。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        nums.sort()  # 将数组排序
        n = len(nums)  # 获取数组长度
        for i in range(n):  # 遍历排序后的数组
            if nums[i] >= k:  # 找到第一个大于等于 k 的元素
                return i  # 返回其索引，即为需要移除的元素数量

Explore

在这个问题中，选择对数组进行排序是因为它简单直观并且适用于任何数值范围的输入。计数排序虽然在特定条件下（如数据范围小且整数）效率更高，但它需要额外的空间来存储每个数的计数，并且不适用于大范围或非整数数据。直接遍历计算虽然可以避免排序的时间成本，但需要多次遍历来确定移除元素的最小数量，效率可能不如排序后一次遍历确定。因此，通用的排序方法在未明确数据范围和类型时是一个稳妥的选择。

排序后的数组是按照数值大小升序排列的。所有小于 k 的元素都会被排列在数组的前部，而所有大于等于 k 的元素则位于后部。因此，第一个大于等于 k 的元素的索引（即数组中的位置）恰好表示了所有小于 k 的元素的数量。这个索引值直接告诉我们需要移除多少个小于 k 的元素以满足条件，因为这些元素位于数组的前面并且被连续计数。

如果数组中所有元素都大于等于 k，这意味着没有任何元素需要被移除，因为所有元素已经满足大于等于 k 的条件。在这种情况下，题解应该返回 0，因为不需要进行任何移除操作。题解中提到返回索引值可能是考虑到通常情况下的处理，但对于这种特殊情况，返回 0 是更准确的答案。