Bài Toán Tìm Chênh Lệch Nhỏ Nhất và Lớn Nhất

Mô Tả Bài Toán

Bạn được cung cấp một mảng số nguyên nums. Trong mỗi lần di chuyển, bạn có thể chọn một phần tử bất kỳ trong mảng và thay đổi nó thành một giá trị mới. Nhiệm vụ của bạn là tìm giá trị nhỏ nhất của chênh lệch giữa phần tử lớn nhất và nhỏ nhất trong mảng sau khi thay đổi tối đa ba phần tử.

Ví Dụ

Đầu vào:

nums = [1, 5, 6, 14, 15]  

Giải thích:

• Bước 1: Chọn 1 và thay đổi thành 14 → [14, 5, 6, 14, 15]
• Bước 2: Chọn 5 và thay đổi thành 14 → [14, 14, 6, 14, 15]
• Bước 3: Chọn 6 và thay đổi thành 14 → [14, 14, 14, 14, 15]

Kết quả là giá trị chênh lệch nhỏ nhất giữa phần tử lớn nhất và nhỏ nhất ở đây là 15 - 14 = 1.
Đáp án là: 1

Hướng Tiếp Cận Giải Quyết Bài Toán

Chiến Lược Giải Quyết

Giả sử n là độ dài của mảng nums, ta có thể nhóm các tình huống như sau:

1. Nếu không thay đổi phần tử nào, kết quả sẽ là nums[n-1] - nums[0]
2. Nếu thay đổi một phần tử, cần tính toán min của (giá trị thứ hai lớn nhất trong nums - phần tử nhỏ nhất, phần tử lớn nhất - giá trị thứ hai nhỏ nhất trong nums)

Tương tự, với trường hợp thay đổi tối đa ba phần tử, chúng ta có bốn chiến lược sau:

1. Loại bỏ ba phần tử lớn nhất.
2. Loại bỏ hai phần tử lớn nhất và một phần tử nhỏ nhất.
3. Loại bỏ một phần tử lớn nhất và hai phần tử nhỏ nhất.
4. Loại bỏ ba phần tử nhỏ nhất.

Thuật Toán Giải Quyết

Chúng ta có thể sử dụng hai thuật toán sau để thực hiện các tính toán trên:

def minDifference(self, nums: List[int]) -> int:
    if len(nums) < 5:
        return 0
    nums.sort()
    n = len(nums)
    return min(nums[n-4] - nums[0], nums[n-3] - nums[1], nums[n-2] - nums[2], nums[n-1] - nums[3])

def minDifference2(self, nums: List[int]) -> int:
    if len(nums) < 5:
        return 0
    nums.sort()
    return min(abs(b-a) for a, b in zip(nums[-4:], nums[:4]))

Tham Khảo

Để biết thêm chi tiết, vui lòng tham khảo bài viết trên LeetCode.
source: viblo