题目地址: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