Chương trình tìm mảng con độ dài k có độ bất công nhỏ nhất trong Python

Cho mảng A và số k. Chọn k phần tử từ A tạo mảng arr sao cho "độ bất công" = max(arr) - min(arr) nhỏ nhất.

Ví dụ: A = [25, 120, 350, 150, 2500, 25, 35], k = 3 → kết quả 10. Chọn [25, 25, 35], max=35, min=25, chênh=10.

Thuật toán giải quyết (O(n log n))

1. Sắp xếp A tăng dần
2. Duyệt cửa sổ kích thước k: với mỗi i từ 0 đến n-k, tính A[i+k-1] - A[i]
3. Trả về giá trị nhỏ nhất

Chứng minh: tập k phần tử tối ưu luôn là k phần tử liên tiếp trong mảng đã sắp xếp.

Ví dụ minh họa

def solve(A, k):
    i = 0
    A.sort()
    n = len(A)
    m = A[n-1]
    while i < n - k:
        if A[i+k-1] - A[i] < m:
            m = A[i+k-1] - A[i]
        i += 1
    return m

A = [25, 120, 350, 150, 2500, 25, 35]
k = 3
print(solve(A, k))

Đầu vào

[25, 120, 350, 150, 2500, 25, 35]

Đầu ra

10