561.数组拆分 I (Easy)*

题目描述*

给定长度为 2n 的数组，你的任务是将这些数分成 n 对，使得从 1 到 n 的 min(ai, bi) 总和最大。

提示*

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

代码*

排序之后求奇数位和就行。

class Solution {
public:
    void quickSort(vector<int>& nums, int l, int r) {
        if(l < r) {
            swap(nums[l], nums[rand() % (r - l + 1) + l]);
            int pivot = nums[l];
            int start = l, end = r;
            while(start < end) {
                while(start < end && nums[end] >= pivot) {
                    end--;
                }
                if(start < end) {
                    nums[start] = nums[end];
                    start++;
                }
                while(start < end && nums[start] <= pivot) {
                    start++;
                }
                if(start < end) {
                    nums[end] = nums[start];
                    end--;
                }
                nums[start] = pivot;
            }
            quickSort(nums, l, start - 1);
            quickSort(nums, start + 1, r);
        }
    }
    int arrayPairSum(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        int sum = 0;
        for(int i = 0; i < nums.size(); i += 2) {
            sum += nums[i];
        }
        return sum;
    }
};

最后更新: July 23, 2022