array-partition-i

Array Partition I – LeetCode 561

Problem

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.

Answer

Original

Code

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

思路

简单排序之后两个两个取其中第一个。时间复杂度$O(log(n))$，空间复杂度$O(1)$。
耗时$52$ ms，排名$13.02\%$

Better

思路

还没看到更好的算法。