LeetCode-561-数组拆分 I

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。

image.png

解题思路：

1. 先排序，后取pair的前一个数；
2. 桶排序，空间换时间

Python3代码：

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        # nums.sort()
        # ans = 0 
        # i = 0 
        # while i < len(nums):
        #     ans+= min(nums[i], nums[i+1])
        #     i += 2
        # return ans
        bucket = [0]* 20001
        for num in nums:
            bucket[num+10000] += 1
        i = 0
        res = 0
        while True:
            while i<20001 and bucket[i]==0:
                i += 1
            if i==20001:
                break
            res += i-10000  # 取前一个数
            bucket[i] -= 1
            while bucket[i] == 0:
                i += 1
            bucket[i] -= 1
        return res