链接
https://leetcode-cn.com/problems/array-partition-i/
耗时
解题：5 min
题解：24 min
题意
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
思路
分成 n 对，每对里取最小的加和，那么朴素的贪心想法就是每对里面较小的元素尽可能的大，较大的元素只比较小的元素大一点就好，那么一对中的两个元素的大小是挨着的就符合这种想法。进一步地，排个序，按排序后的数组顺序两两一对，这就是最优方案，并且排序后的数组中奇数位的元素即是每对中较小的元素，它们的和即是答案。
时间复杂度：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
AC代码
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0;
int n = nums.size();
for(int i = 0; i < n; ++i) {
if((i&1) == 0) {
ans += nums[i];
}
}
return ans;
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
