题目描述:两句话发人深思啊。。。。
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.
感觉题目的大致意思就是把数组分成很多个二元数组,对它们以求最小值的方式求和,使得和最大。
思路:
最开始的思路,现在还不知道对不对,就是先排序数组,使用一个指针向后遍历,求最小并求和。⚠️【注意】指针每次累加 2
【正确代码】 一次写对~
class Solution {
public int arrayPairSum(int[] nums) {
if (nums.length % 2 != 0 || nums == null) {
return -1;
}
Arrays.sort(nums);
int maxSum = 0;
for (int i = 0; i < nums.length - 1; i += 2) {
maxSum += Math.min(nums[i], nums[i + 1]);
}
return maxSum;
}
}
时间复杂度:O(n*logn)
空间复杂度:O(n*logn)