超过阈值的最少操作数 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 存在。

解题思路

要解决这个问题，首先需要对数组 nums 进行排序。排序后，数组中的最小元素将位于数组的起始位置。从数组的最小端开始，每遇到一个小于 k 的元素，就将其删除，并将操作计数器加一。当遇到第一个大于或等于 k 的元素时，停止删除操作。

给定一个从 0 开始的整数数组 nums 和一个整数 k，目的是通过最少的操作次数使数组中的所有元素都大于或等于 k。操作定义为删除数组中的最小元素。

算法步骤

  1. 对数组 nums 进行排序。
  2. 初始化操作计数器为 0。
  3. 遍历排序后的数组，对于每个小于 k 的元素，增加操作计数。
  4. 当遇到第一个大于或等于 k 的元素时，停止遍历。
  5. 返回操作计数。

解决方案

算法思路

  1. 排序数组：首先将数组排序，这样可以确保我们总是在执行操作时删除最小的元素。
  2. 计数操作：从数组的最小端开始，对于每个小于 k 的元素，我们将其删除，并增加操作计数器。
  3. 停止条件：当数组中所有剩余的元素都大于或等于 k 时，操作结束。

算法步骤

  1. 对数组 nums 进行排序。
  2. 初始化一个操作计数器。
  3. 遍历排序后的数组，对于每个小于 k 的元素，增加操作计数。
  4. 当遇到第一个大于或等于 k 的元素时，停止遍历。
  5. 返回操作计数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def min_operations(nums, k):
    # Sort the array
    nums.sort()

    # Count the number of operations
    operations = 0
    for num in nums:
        if num < k:
            operations += 1
        else:
            break

    return operations

测试用例

1
2
3
print(min_operations([2, 11, 10, 1, 3], 10))  # 应输出: 3
print(min_operations([1, 1, 2, 4, 9], 1))     # 应输出: 0
print(min_operations([1, 1, 2, 4, 9], 9))     # 应输出: 4

复杂度分析

  • 时间复杂度：O(n log n)，主要由排序步骤决定。
  • 空间复杂度：O(n) 或 O(1)，取决于所使用的排序算法。如果使用原地排序算法，空间复杂度可以降低到 O(1)。

结论

这个解决方案通过排序和简单的线性遍历，有效地找出了将数组中所有元素变得大于或等于 k 所需的最少操作次数。它适用于不同的输入场景，并且在时间和空间效率方面表现良好。