题目地址：https://leetcode.com/problems/array-partition-i/description/

题目描述

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 $(a_1, b_1), (a_2, b_2), …, (a_n, b_n)$ ，使得从1 到 n 的 $min(a_i, b_i)$ 总和最大。

示例 1:
输入: [1,4,3,2]
输出: 4

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

提示:

  • n 是正整数,范围在 [1, 10000].
  • 数组中的元素范围在 [-10000, 10000].

解题思路

刚开始没看懂题目中的拆分是怎么拆分的。。。后来根据题目的例子做，先把数组从小到大排序，比如[1,4,3,2]，排序后为[1,2,3,4], 然后按照一次取出两个数字(pop方法)，依次取出数组中的数，即(1,2),(3,4)，再对两个数字取最小的那个，最后将所有最小的求和。

通过代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = sorted(nums)
        res = 0
        n = len(nums)//2
        for i in range(n):
            res += min(nums.pop(0), nums.pop(0))
        return res

这样的做的Runtime: 360 ms，排名很靠后。。

看别人的代码：

1
2
3
4
5
6
7
8
class Solution(object):

    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(sorted(nums)[::2])

比如排序后数组nums = [1,2,3,4,5,6,7,8], 依次取出两个数字为(1,2), (3,4), (5,6), (7,8), 每两个数字的最小值为1,3,5,7，就是nums[::2]

少了我的那些不必要的pop操作，Runtime: 120 ms