LeetCode-Array Partition I

来源：恒创科技编辑：恒创科技编辑部

2024-01-25 22:00:59

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

题意：给定一个有2n个元素的数组，要求将数组划分为n对(a1, b1), (a2, b2), …, (an, bn)，返回一个和sum满足

sum=∑i=1nmin(ai,bi) s u m = ∑ i = 1 n m i n ( a i , b i )

解法：要想让最后得到的和最大，那么划分的n对中的值小的应该和值小的成一对，值大的应该和值大的一对，这样子大的值才会被保留，所以我们先对数组进行排序后，那么，相邻的两个元素自然成为了一对，再对两个元素中的小值进行累加求和;

class Solution
    public int arrayPairSum(int[] nums) {
        int sum = 0;
        Arrays.sort(nums);
        for(int i=0; i<nums.length-1;) {
            sum += nums[i];
            i += 2;
        }
        return sum;
    }
}

本文地址：https://www.henghost.com/jishu/19318/