這題的題目在這裡: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.length2 <= n <= 10^5nis 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:
