Minimum number of operations above threshold I

title

Given an array of integers indexed starting from 0 nums and an integer k. In each operation you can delete nums the smallest element in . The goal is to make all elements in the array greater than or equal to the minimum number of operations k. Needs to return the minimum number of operations required to achieve this goal.

Example

Example 1:

• Input:nums = [2, 11, 10, 1, 3], k = 10
• Output:3
• Explanation:
  • After the first operation,nums become [2, 11, 10, 3]。
  • After the second operation,nums become [11, 10, 3]。
  • After the third operation,nums become [11, 10]。
  • At this point, all elements in the array are greater than or equal to 10, so stop the operation.
  • Make all elements in the array greater than or equal to 10 The minimum number of operations required is 3。

Example 2:

• Input:nums = [1, 1, 2, 4, 9], k = 1
• Output:0
• Explanation: All elements in the array are greater than or equal to 1, so there is no need to nums Do any operation.

Example 3:

• Input:nums = [1, 1, 2, 4, 9], k = 9
• Output:4
• Explanation:nums Only one element in is greater than or equal to 9, so it is necessary to execute 4 operations.

Tips

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9
• The input is guaranteed to satisfy at least one nums[i] >= k subscript i exists.

Problem-solving ideas

To solve this problem, we first need to nums to sort. After sorting, the smallest element in the array will be at the beginning of the array. Starting from the smallest end of the array, each time it encounters a value less than k element, delete it and increase the operation counter by one. When encountering the first greater than or equal to k of elements, stop the deletion operation.

Given an array of integers starting from 0 nums and an integer k, the purpose is to make all elements in the array greater than or equal to the smallest number of operations k. The operation is defined as removing the smallest element from the array.

Algorithm steps

1. pair array nums to sort.
2. The initialization operation counter is 0。
3. Iterate over the sorted array, for each item less than k element, incrementing the operation count.
4. When encountering the first greater than or equal to k of elements, stop traversing.
5. Returns the operation count.

solution

Algorithm ideas

1. sort array: Sort the array first, this ensures that we always remove the smallest element when performing an operation.
2. counting operation: Starting from the smallest end of the array, for each item less than k element, we remove it and increment the operation counter.
3. Stop condition: When all remaining elements in the array are greater than or equal to k when, the operation ends.

Algorithm steps

1. pair array nums to sort.
2. Initialize an operation counter.
3. Iterate over the sorted array, for each item less than k element, incrementing the operation count.
4. When encountering the first greater than or equal to k of elements, stop traversing.
5. Returns the operation count.

Code implementation

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

test case

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

Complexity analysis

• time complexity:O(n log n), mainly determined by the sorting step.
• space complexity: O(n) or O(1), depending on the sorting algorithm used. If an in-place sorting algorithm is used, the space complexity can be reduced to O(1).

Conclusion

This solution effectively finds all elements in the array that become greater than or equal to k Minimum number of operations required. It is suitable for different input scenarios and performs well in terms of time and space efficiency.