Giả sử chúng ta có một danh sách các số gọi là nums, và một giá trị k. Nếu chúng ta xóa k phần tử từ nums, hãy tìm min(max(nums) - min(nums)).
Vì vậy, nếu đầu vào là nums = [4, 10, 3, 2, 8, 9] k = 3, thì đầu ra sẽ là 2, vì nếu xóa 10, 8 và 9 thì max là 4, min là 2 nên hiệu là 2.
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:
sắp xếp danh sách nums
p := kích thước nums - k
m := (phần tử cuối của nums) - nums[0]
với i trong khoảng 0 đến kích thước nums - p, thực hiện
nếu nums[i + p - 1] - nums[i] < m, thì m := nums[i + p - 1] - nums[i]
trả về m
Ví dụ
Hãy xem triển khai sau để hiểu rõ hơn:
def solve(nums, k):
nums = sorted(nums)
p = len(nums) - k
m = nums[-1] - nums[0]
for i in range(0, len(nums) - p + 1):
if nums[i + p - 1] - nums[i] < m:
m = nums[i + p - 1] - nums[i]
return m
nums = [10, 4, 3, 2, 9, 8]
k = 3
print(solve(nums, k))
Đầu vào
[10, 4, 3, 2, 9, 8], 3
Đầu ra
2