题目描述

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

样例

输入: [1,4,3,2]

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

注意

• n 是正整数，范围在 [1, 10000]。
• 数组中的整数范围在 [-10000, 10000]。

算法

(贪心) $O(n \log n)$

1. 很容易想到，让两个比较小的数在一起比一个小的一个大的数放在一起产生的结果要大。
2. 故可以先将数组排序，然后从头开始相邻两个整数放在一起，这样子可以产生最大的结果。

时间复杂度

• 对数组进行排序，故时间复杂度为 $O(n \log n)$。

C++ 代码

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