0561. Array Partition

题目信息

题号:

0561

难度:

Easy

主题:

偶数长度数组、两两分组、较小值之和、最大化

原题:

LeetCode 0561

重点:

所有元素必须恰好分入 n 个二元组、每组贡献较小值、返回最大可能总和

题目重述

给定一个长度为 2n 的整数数组 nums,需要把全部元素划分为 n 个二元组 (a_i, b_i)。每个数组位置必须恰好属于一个二元组。

每组贡献 min(a_i, b_i),返回所有组贡献之和能够达到的最大值。相同数值位于不同下标时仍是不同元素,必须分别参与分组。

自建示例

六个元素分成三组:

输入:nums = [1,4,3,2,7,6]
输出:10
解释:可分为 (1,2)、(3,4)、(6,7),较小值之和为 1+3+6=10,并且无法取得更大总和。

包含负数:

输入:nums = [-4,-1,2,3]
输出:-2
解释:分组 (-4,-1) 与 (2,3) 的较小值之和为 -4+2=-2,是最大结果。

排序后相邻配对保留更多较小值

排序数组后把相邻元素配成一对。若跨越配对让一个较大的元素成为某组最小值,就会放弃一个本可保留的较小值;交换配对可以不降低总和,反复交换后得到相邻配对。因此排序后每隔一个元素累加就是最优值。

C++ 实现

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

代码分析

每一对的贡献是其较小者,排序相邻配对能让每个较小者尽量不被更大的元素替代;这是最大化保留下界的贪心结构。排序耗时 O(n log n),扫描为 O(n),额外空间为 ``O(1)``(不计排序栈)。