動機

當初以為只要把最大或最小3個去掉就好…

Problem

Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.

Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.

 

Example 1:

Input: nums = [5,3,2,4]Output: 0Explanation: Change the array [5,3,2,4] to [2,2,2,2].The difference between the maximum and minimum is 2-2 = 0.

Example 2:

Input: nums = [1,5,0,10,14]Output: 1Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1]. The difference between the maximum and minimum is 1-0 = 1.

Example 3:

Input: nums = [6,6,0,1,1,4,6]Output: 2

Example 4:

Input: nums = [1,5,6,14,15]Output: 1

 

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Sol

sort，會有4個case

  • 3大
  • 1小2大
  • 2小1大
  • 3小
class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        else:
            nums.sort()
            return min(nums[-4]-nums[0], nums[-3]-nums[1], nums[-2]-nums[2], nums[-1]-nums[3])

可以只sort一部分嗎?

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        else:
            return min(a - b for a,b in zip(heapq.nlargest(4, nums), heapq.nsmallest(4, nums)[::-1]))