Chương trình tối thiểu hóa độ lệch mảng trong Python

Mô tả bài toán

Cho mảng nums. Có thể thực hiện: số chẵn chia 2, số lẻ nhân 2 (bất kỳ lần nào). Độ lệch = max - min. Tìm độ lệch tối thiểu.

Ví dụ

nums = [6,3,7,22,5] -> 5 (biến thành [6,6,7,11,10], max=11, min=6).

Giải thuật (Heap)

1. Sắp xếp, khởi tạo min-heap, max_v, min_v, res = max_v - min_v.
2. Trong khi phần tử nhỏ nhất là lẻ: pop, nhân 2, push lại, cập nhật min_v, max_v, res.
3. Đảo dấu mảng thành max-heap (lưu giá trị âm).
4. Trong khi phần tử lớn nhất (dương) là chẵn: pop, chia 2, push lại, cập nhật max_v, min_v, res.

Triển khai Python

import heapq

def solve(nums):
    nums.sort()
    max_v, min_v = nums[-1], nums[0]
    heapq.heapify(nums)
    res = max_v - min_v
    while nums[0] % 2 == 1:
        v = heapq.heappop(nums)
        v = 2 * v
        heapq.heappush(nums, v)
        min_v = nums[0]
        max_v = max(v, max_v)
        res = min(res, max_v - min_v)
    nums = [-n for n in nums]
    heapq.heapify(nums)
    while nums[0] % 2 == 0:
        v = -heapq.heappop(nums)
        v = v // 2
        heapq.heappush(nums, -v)
        max_v = -nums[0]
        min_v = min(min_v, v)
        res = min(res, max_v - min_v)
    return res

nums = [6, 3, 7, 22, 5]
print(solve(nums))

Đầu vào

[6,3,7,22,5]

Đầu ra

5