题目

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

示例 1:

输入: [1,4,3,2]

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).

来源：https://leetcode-cn.com/problems/array-partition-i

解题思路

要想使 min(a,b) 和最大，则要避免差值过大的两个数相结合。
因此我们对给定长度 2n 的数组进行排序，对于这个排好序的数组，要想使 min（a，b）和最大，排序数组倒数第二个数，即把问题分解为求长度 2n-2 的数组 min(a，b) 与 arr[2n-2] 的最大和。

继续分解直到到最后 2 个数取 arr[0]。因此问题转化为求排序数组奇数位的和: arr[0]+arr[2]+…arr[2n-2]。

借鉴官方题解的第三种解法。将排序 O(nlogn) 的复杂度通过哈希降为 O(n)，而代价就是哈希结构额外的内存空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def arrayPairSum(self, nums):
        # 哈希记录 -10000～10000 每个数的出现次数,未出现则为 0
        arr = [0]*20001
        offset = 10000
        for num in nums:
           arr[offset + num] += 1
        
        res = 0
        #当同一个数字出现多次时 根据 x 决定取数字的次数
        x = 1
        for i in range(0,20001):
            if arr[i] > 0:
                res += (arr[i] + x)//2 * (i - offset)
                if arr[i] % 2 != 0:
                    # python 没有三目和取反运算符 使用 if-else 
                    if x == 0:
                        x = 1
                    else:
                        x = 0 
        return res

分析

时间复杂度：O(n)。需要遍历一次哈希表 arr。
空间复杂度：O(n)。存储一个大小为n哈希表 arr 所需要的空间。