最小化pair sum的極大值 Minimize Max Pair Sum in Array_Leetcode 1877

Tim Chow on Unsplash

這題的題目在這裡:Minimize Maximum Pair Sum in Array

題目敘述

題目會給我們一個整數陣列nums，裡面都是正整數，而且陣列長度保證是偶數。

要求我們倆倆將所有整數配對成一組pair，要求我們最小化pair sum的極大值。

舉例，[1,2,3,4]

最佳解為

1,4 配對，pair sum = 5

2,3 配對，pair sum = 5

回傳答案 最小化pair sum的極大值max(5, 5) = 5

註: 其他配對情況，所產生的最小化pair sum的極大值都比5還大

測試範例

Example 1:

Input: nums = [3,5,2,3]
Output: 7
Explanation: The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.

Example 2:

Input: nums = [3,5,4,2,4,6]
Output: 8
Explanation: The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.

約束條件

Constraints:

• n == nums.length
• 2 <= n <= 10^5
• n is even.
• 1 <= nums[i] <= 10^5

演算法

先用比較小的模型來想

假設只有四個數字，a <= b <= c <= d

那麼最佳配對方法為何?

最佳配對方法是: (a, d) 和 (b, c)

max(a+d, b+c) 會是最終答案

這邊用反證法去證明

假如不這麼配呢?

假如(a, c) 和 (b, d)一組

b + d >= a + d (從兩邊等量相加d得到)

b + d >= b + c (從兩邊等量相加b得到)

max(a+c, b+d) >= b + d >= max(a+d, b+c)

所以不是最佳解

假如(a, b) 和 (c, d)一組

c + d >= a + d (從兩邊等量相加d得到)

c + d >= b + c (從兩邊等量相加c得到)

max(a+b, c+d) >= c + d >= max(a+d, b+c)

所以不是最佳解

其他更多數字的情況，可以用類似的手法去推廣證明。

最後歸納可以發現，最佳解的配對方法，就是

最小的數字 配 最大的數字

第二小的數字 配 第二大的數字

第三小的數字 配 第三大的數字

...

依此類推

所以，先把輸入陣列作排序由小到大升序排列。

接著，從頭尾開始配對，往中心前進，過程中，得到的配對最大值，就是整個陣列元素配對的最小化pair sum的極大值

程式碼

class Solution:
　def minPairSum(self, nums: List[int]) -> int:

　　# Keep nums sorted in ascending order
　　nums.sort()

　　left, right = 0, len(nums)-1
　　optimal = 0

　　# Keep each pair sum as near as possible
　　# one from current smallest, one from current largest
　　while left < right:

　　　cur_pair = nums[left] + nums[right]
　　　optimal = max(optimal, cur_pair)

　　　left, right = left+1, right-1

　　return optimal
　　

複雜度分析

時間複雜度: O(n log n)

陣列排序，耗費O(n log n)

迴圈，線性掃描，耗費O(n)

總時間成本，取大的，最後是O( n log n)

空間複雜度: O(1)

所用到的都是固定尺寸的臨時變數，為常數級別O(1)

關鍵知識點

最後歸納可以發現，最佳解的配對方法，就是

最小的數字 配 最大的數字

第二小的數字 配 第二大的數字

第三小的數字 配 第三大的數字

...

依此類推

所以，先把輸入陣列作排序由小到大升序排列。

接著，從頭尾開始配對，往中心前進，過程中，得到的配對最大值，就是整個陣列元素配對的最小化pair sum的極大值

Reference:

[1] Python O(n log n ) by sorting and two-pointers [w/ Comment] - Minimize Maximum Pair Sum in Array - LeetCode