leetcode561--Array Partition I

leetcode561--Array Partition I

题目

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

解法

其实这个题目主要是理解其中的想法,因为是任意配对,就不妨假设给的这个数组是从小到大排好顺序的好了,[x0,x1,x2,...,xn,...],那么现在想一想最小的x0应该与哪个配对. 如果x0没有与x1配对,那么x1一定会出现在最后的加项里面,那这一定没有把x0x1配对时的结果大。因为其它的都要比x1大。 所以x0该与x1配对,同样的道理可以分析x2该与x3配对,所以就很明了了。

代码如下

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

或者用 python

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ret = 0
        nums = sorted(nums)
        for i in range(0,len(nums),2):
            ret +=nums[i]
        return ret
            

或者更简单的直接return sum(sorted(ret)[::2]).

但是上面的基于排序的算法时间复杂度至少是o(nlogn),有没有更好的办法呢,有很多条件其实都还没有用到呢,比如给的数的范围,也可以从这里想办法。 其实下面也未心是更好的办法,只不过是另一种思路

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        Help = [0]*(20001)
        for x in nums:
            Help[x+10000] += 1   # 有的值可能出现2次以上。
            
        ret = 0
        flag = True
        for i in range(len(Help)):
            while Help[i]:   
                if flag:
                    ret += (i-10000)
                Help[i] -= 1
                flag = not flag
        return ret
                

想法是这样的,先申请长为20001都是0的数组Help,然后遍历nums,有值的话就加1, 相当于是Help中的数字如果不为0的话,代表出现在了nums中,如果大于1的话,说明出现了还不止一次。 然后开始遍历整个Help,在不是0的地方,要加个while去遍历,因为这个数可能出现多次,第一次的时候相当于是最小的数字,那么下一次就不能加了,所以用flag = not flag即要跳着加。每加一次Help要减1,因为这个数可能复复。比如[1,2,2,3]。

用c++的话是


class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        vector<int> t(20001);
        for(int& i : nums)
            t[i + 10000]++;
        
        // 这时候不为0的那些位置代表nums
    
        int ans = 0;
        bool evenNum = true;
        for(int j = 0; j < t.size(); ++j){
            while(t[j]){
                if(evenNum)
                    ans+=(j-10000);
                t[j]--;
                evenNum = !evenNum;
            }
        }
        return ans;
    }
};

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦