LeetCode 561. Array Partition I

1.问题描述

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].

2.算法分析

根据问题的描述可知，问题的解应该为把原始数组按照升序进行排序，再把奇数位置上的数组元素进行求和，即为所求。

算法证明如下（来源于参考链接）：

假设对于每一对（ai，bi)，都有bi >= ai。定义Sm = min（a1，b1）+ min（a2，b2）+ … + min（an，bn）。最大的Sm是这个问题的答案。由于bi >= ai，Sm = a1 + a2 + … + an。定义Sa = a1 + b1 + a2 + b2 + … + an + bn。对于给定的输入，Sa即为整个数组的和，是一个常数。定义di = | ai - bi |。由于bi >= ai，所以di = bi-ai, 即bi = ai+di。定义Sd = d1 + d2 + … + dn。所以Sa = a1 + (a1 + d1) + a2 + (a2 + d2) + … + an + (an + di) = 2Sm + Sd , 所以Sm =（Sa-Sd）/ 2。为得到最大Sm，给定Sa为常数，需要使Sd尽可能小。所以这个问题就是在数组中找到使di（ai和bi之间的距离）的和尽可能小的对。显然，相邻元素的这些距离之和是最小的。

参考链接：

1) https://blog.csdn.net/whl_program/article/details/70667333 2) https://leetcode.com/problems/array-partition-i/discuss/102170/java-solution-sorting-and-rough-proof-of-algorithm

3.代码实现

3.1 方法1

对原始输入数组进行排序，开始我采用的是冒泡排序，时间复杂度为O(n^2)，严重超时，此处不赘述，也可以采用其他更快速的排序。

3.2 方法2

使用标准库函数sort()对数组排序， 然后对奇数位置上的数组元素求和。C++实现code如下：

class Solution { public: int arrayPairSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int sum = 0; for(int i = 0; i<nums.size(); i+=2){ sum += nums[i]; } return sum; } };

3.3 方法3

由于数组元素是整数，且已知元素的取值范围，所以可用基数排序来减少时间复杂度：

1) 首先创建20001个桶来分别存放数组元素取值个数。

2) 取值为[-10000, 10000]的数组元素的个数分别记在0号桶到20000号桶中，所以元素值nums[i]与桶的编号idx之间的关系为idx= nums[i] + 10000。

3) 由于需要对奇数位置数组求和，所以需要一个标志位flag来标记当前位置是否为奇数位置。

4）如果某个桶里具有多个相同取值的数组元素，那么标志位flag需要交替变换，且只有当当前桶为空时才能遍历下一号桶。

C++实现code如下：

class Solution { public: int arrayPairSum(vector<int>& nums) { vector<int> bucket(20001, 0); for (auto num : nums){ bucket[num + 10000] ++; } bool flag = true;// 控制是否为奇数位，因为所求是值等于升序排序后的数组的奇数位之和 int sum = 0; for (int i = 0; i<bucket.size();){ while (bucket[i]>0){ if (flag == true){ sum += i - 10000; bucket[i]--; flag = false; } else{ bucket[i]--; flag = true; } } i++; } return sum; } };