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

### 解法

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;
}
};

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

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

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;
}
};