LeetCode：(Array)(Python)Array Partition

題目連結：https://leetcode.com/problems/array-partition/description/

有一個 List，其中數字個數為偶數

將所有數字兩兩分組，從每組找出較大數字，加總較大數值後回傳

看一個範例就可以理解

初始想法一

1. 將List由小排到大
2. 每兩格加總一次

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        max_number = 0

        for i in range(0,len(nums),2):
            max_number = max_number + nums[i]

        return max_number

初始想法二

1. 每個迴圈都對 List取 max()
2. 第 1,3,5,7, . . .奇數個迴圈的值加總儲，偶數迴圈跳過

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        max_number = 0
        is_add = 0
        
        while len(nums) > 0:
            if is_add == 1:
                max_number = max_number + max(nums)
                is_add = 0
            else:
                is_add = 1

            nums.remove(max(nums))

        return max_number

            

這個會跑到超時，每次都取 Max等於不斷在 scan

初始想法三

1. 排序 List
2. 每兩格加總一次，但是用 List語法

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[0:(len(nums)-1):2])

參考他人解法

解法連結：https://leetcode.com/problems/array-partition/solutions/3079728/beats-99-16-2-liner-python-solution/?orderBy=hot&languageTags=python

和我的初始想法三很相似，但更簡潔

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

2024-09-04

有些不理解為何排序後在兩兩取值就會是最大的最小值組合，因此問了 ChatGPT。

兩兩一組，每組選出最小值，但總和每組要是最大值，代表每組的兩個數字之間差異越少越好。

兩個數字差異越小，min()越接近取 max()的概念

以範例來說

1和2一組 -> min = 1, max =2，min 和 max 差1

3和4一組 -> min = 3, max =4，min 和 max 差1

1和4一組 -> min = 1, max =4，min 和 max 差3

2和3一組 -> min = 2, max =3，min 和 max 差1

1和4一組就浪費了4