leetcode 561. Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a₁, b₁), (a₂, b₂), ..., (a_n, b_n) which makes sum of min(a_i, b_i) 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:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].  

1. 解法：

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # [1,4,3,2]=>sort, [1,2,3,4]=>1+3=4
        # [1,2,3,5,12,19,20,21]=>sorted => greedy, 1+3+12+20
        nums.sort()
        return sum(nums[0::2])

我自己想的是贪心思路，

先假设这个数组排序了，例如：[1,2,3,5,12,19,20,21]

min(ai, bi)明显是Min（20，21），因为21最大。

剩下的就是递归解：

[1,2,3,5,12,19】

思路类似。

其他人的分析：

Let me try to prove the algorithm…

1. Assume in each pair i, bi >= ai.
2. Denote Sm = min(a1, b1) + min(a2, b2) + ... + min(an, bn). The biggest Sm is the answer of this problem. Given 1, Sm = a1 + a2 + ... + an.
3. Denote Sa = a1 + b1 + a2 + b2 + ... + an + bn. Sa is constant for a given input.
4. Denote di = |ai - bi|. Given 1, di = bi - ai. Denote Sd = d1 + d2 + ... + dn.
5. So Sa = a1 + a1 + d1 + a2 + a2 + d2 + ... + an + an + dn = 2Sm + Sd => Sm = (Sa - Sd) / 2. To get the max Sm, given Sa is constant, we need to make Sd as small as possible.
6. So this problem becomes finding pairs in an array that makes sum of di (distance between ai and bi) as small as possible. Apparently, sum of these distances of adjacent elements is the smallest. If that’s not intuitive enough, see attached picture. Case 1 has the smallest Sd.

其他解法就是trick，利用All the integers in the array will be in the range of [-10000, 10000].hash来做桶排序。

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # bucket sort
        num_range = 20001
        sort_map = [0]*num_range
        for n in nums:
            sort_map[n+10000] += 1
        ans = 0
        odd = True
        for i in range(0, num_range):
            while sort_map[i]:
                if odd:
                    ans += (i-10000)
                sort_map[i] -= 1
                odd = not odd
        return ans