Cho mảng nums. Mỗi phép thay đổi cho phép gán giá trị bất kỳ cho một phần tử. Tìm hiệu số nhỏ nhất giữa phần tử lớn nhất và nhỏ nhất sau tối đa 3 phép thay đổi.
Ví dụ: nums = [3,7,2,12,16], kết quả là 1 vì có thể biến mảng thành [1,1,0,1,1] (hoặc các giá trị gần nhau), max = 1, min = 0, hiệu = 1.
Thuật toán giải quyết
- Nếu độ dài nums ≤ 4, trả về 0 (có thể làm tất cả bằng nhau).
- Sắp xếp mảng nums.
- ans := vô cực.
- Với i từ 0 đến 3:
- mi := nums[i] (phần tử nhỏ thứ i).
- ma := nums[-(3-i+1)] (phần tử lớn thứ 3-i).
- ans := min(ans, ma - mi).
- Trả về ans.
Ý tưởng: sau 3 phép thay đổi, ta có thể loại bỏ tối đa 3 phần tử nhỏ nhất hoặc lớn nhất. Duyệt 4 trường hợp: loại 0 nhỏ + 3 lớn, 1 nhỏ + 2 lớn, 2 nhỏ + 1 lớn, 3 nhỏ + 0 lớn.
Ví dụ triển khai
def solve(nums):
if len(nums) <= 4:
return 0
nums.sort()
ans = float("inf")
for i in range(4):
mi = nums[i]
ma = nums[-(3-i+1)]
ans = min(ma - mi, ans)
return ans
nums = [3,7,2,12,16]
print(solve(nums))Đầu vào
[3,7,2,12,16]
Đầu ra
1