+1

math solution: Tìm chênh lệch nhỏ nhất và lớn nhất sau khi thay đổi 1 số lần cố định

Bài toán

Bạn được cho một mảng số nguyên nums.

Trong một lần di chuyển, bạn có thể chọn một phần tử bất kỳ trong nums và thay đổi nó thành một giá trị bất kỳ.

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à phần tử nhỏ nhất trong mảng sau khi thực hiện tối đa ba lần di chuyển.

Ví dụ Đầu vào:

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

Bước 1: Đổi 1 thành 14 -> [14,5,6,14,15] Bước 2: Đổi 5 thành 14 -> [14,14,6,14,15] Bước 3: Đổi 6 thành 14 -> [14,14,14,14,15]

Vậy giá trị chênh lệch nhỏ nhất của 2 phần tử max và min ở đây là 15-14 = 1 -> Đáp án: 1

Hướng tiếp cận

Đoạn này mình xin phép viết bằng tiếng anh nhé:

  • Given n is length of nums If we remove zero element, the result is nums [n-1] - nums[0] If we remove one element, the result is min(the second max nums - the min nums,the max nums - the second min nums ) So similarly in case remove three elements, we have 4 strategies:
  • Remove 3 biggest elements
  • Remove two biggest elements, one smallest element
  • Remove one biggest element, two smallest elements
  • Remove 3 smallest elements

Vậy ta có 2 thuật toán cho ra kết quả tương tự như sau:

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]))

Reference


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.