难度: Easy
原题连接
内容描述
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:
Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].
思路 1 - 时间复杂度: O(NlgN)- 空间复杂度: O(1)******
这个就是脑子一想就知道了，想要达到结果，我要尽可能取大一点，那么就是排好序每次取一对中的前一个就行了
例如[1,4,3,2]我们排好序为[1,2,3,4]，然后让我们的pair为[1,2]，[3,4]，这样我们结果就是 1 + 3 = 4，肯定最大
beats 99.32%
class Solution(object):
def arrayPairSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return sum(nums[::2])思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******
因为我们的数字范围只会在[-10000, 10000]之间，所以我们把数字和其出现频率记录到一个字典里面
想象一下, 如果输入为[1,1,1,2,2,2]，我们直到最终会有2个1作为最小值，1个2作为最小值，因为我们的pair是[1,1], [1,2], [2,2]。
所以我们遍历[-10000, 10000]中的数字，如果当前数字在我们的字典里面
- 如果其出现频率freq加上前一个出现在字典里面数字遗留下来的频率remain（可能是1也可能是0）是奇数，那么我们知道现在将会有(freq+1) // 2个当前数字作为较小值
- 如果其出现频率freq加上前一个出现在字典里面数字遗留下来的频率remain（可能是1也可能是0）是偶数，那么我们知道现在将会有(freq+0) // 2个当前数字作为较小值
例如:
如果输入为[1,1,1,2,3,4,4,4],我们的字典为{1: 3, 4: 3, 2: 1, 3: 1}
开始遍历（初始化remain为0，因为显然前面没有数字遗留）:
遍历到第一个数字1在字典里面，频率为3，并且前面没有数字遗留（因为remain=0）。更新remain为1，因为1出现频率加上之前数字遗留次数总和是奇数，所以我们知道最后1的归宿肯定是[1,1], [1,?],因此res += cur_num * ((freq+remain) // 2) 即 res += 1 * 2
遍历到第二个数字2在字典里面，频率为1，但是前面有一个数字遗留（因为remain=1），更新remain为0，因为之前遗留+当前频率总和为2，是偶数。所以我们知道2最后的归宿肯定是[prev, 2],prev不需要管它是谁，但这里我们知道它是1。因此res += cur_num * ((freq+remain) // 2) 即 res += 1 * 0
遍历到第三个数字3在字典里面，频率为1，并且前面没有数字遗留（因为remain=0）。更新remain为1，因为之前遗留+当前频率总和为1，是奇数。所以我们知道3最后的归宿肯定是[3, ?]。因此res += cur_num * ((freq+remain) // 2) 即 res += 3 * 1
遍历到第四个数字4在字典里面，频率为3，但是前面有一个数字遗留（因为remain=1），更新remain为0，因为之前遗留+当前频率总和为4，是偶数。所以我们知道4最后的归宿肯定是[prev, 4]和[4,4] ,prev不需要管它是谁，但这里我们知道它是3。因此res += cur_num * ((freq+remain) // 2) 即 res += 4 * 1
最终res = 2 + 0 + 3 + 4 = 9
完美！
但是在这道题里面这个解法反而更慢，跟测试用例有关系，beats 2.81%
class Solution(object):
def arrayPairSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
lookup = collections.Counter(nums)
res, remain = 0, 0
for num in range(-10000, 10001):
if num in lookup:
remain = 1 if (lookup[num]+remain) & 1 == 1 else 0
res += num * ((lookup[num]+remain) // 2)
return res