超过阈值的最少操作数 I
难度:
标签:
题目描述
You are given a 0-indexed integer array nums, and an integer k.
In one operation, you can remove one occurrence of the smallest element of nums.
Return the minimum number of operations needed so that all elements of the array are greater than or equal to k.
Example 1:
Input: nums = [2,11,10,1,3], k = 10 Output: 3 Explanation: After one operation, nums becomes equal to [2, 11, 10, 3]. After two operations, nums becomes equal to [11, 10, 3]. After three operations, nums becomes equal to [11, 10]. At this stage, all the elements of nums are greater than or equal to 10 so we can stop. It can be shown that 3 is the minimum number of operations needed so that all elements of the array are greater than or equal to 10.
Example 2:
Input: nums = [1,1,2,4,9], k = 1 Output: 0 Explanation: All elements of the array are greater than or equal to 1 so we do not need to apply any operations on nums.
Example 3:
Input: nums = [1,1,2,4,9], k = 9 Output: 4 Explanation: only a single element of nums is greater than or equal to 9 so we need to apply the operations 4 times on nums.
Constraints:
1 <= nums.length <= 501 <= nums[i] <= 1091 <= k <= 109- The input is generated such that there is at least one index
isuch thatnums[i] >= k.
代码结果
运行时间: 23 ms, 内存: 16.0 MB
/*
题目思路：
1. 使用Java Stream API来过滤和计数数组中小于k的元素。
2. 使用filter方法筛选出所有小于k的元素，使用count方法统计数量。
3. count的结果即为所需的最少操作次数。
*/
import java.util.Arrays;
public class Solution {
public int minOperations(int[] nums, int k) {
return (int) Arrays.stream(nums)
.filter(num -> num < k)
.count();
}
}解释
方法:
首先对数组进行排序，使得所有元素按照升序排列。排序后，数组中小于 k 的元素都会出现在数组的前面，大于等于 k 的元素会出现在后面。通过遍历排序后的数组，找到第一个大于等于 k 的元素的位置，该位置的索引即是需要移除的元素数量，因为所有小于 k 的元素都需要被移除以满足题目要求。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在这个问题中选择对数组进行排序而不是使用其他方法如计数排序或直接遍历计算？
▷🦆
排序后，如何确保找到的第一个大于等于 k 的元素的索引确实代表了需要移除的元素数量？
▷🦆
在数组全部元素都大于等于 k 的情况下，题解中提到返回索引值，但实际上应该返回什么？
▷