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:
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：
1.n is a positive integer, which is in the range of [1, 10000].
2.All the integers in the array will be in the range of [-10000, 10000].
思路：在一個有序數(shù)組中骂铁，兩兩之間取最小值才能將損失的差值彌補到最小吹零，使所求得的和最大。因而應(yīng)先排序再間隔取值求和拉庵。
問題：
一開始嘗試了最簡單的兩層for循環(huán)排序灿椅，之后再間隔取值加和，但是這樣超出了運行時間要求钞支。
改變思路茫蛹，先遍歷整個數(shù)組，將數(shù)組中的值按順序?qū)懭胄聰?shù)組中烁挟，未存入時標(biāo)志為0婴洼，存入置為1，取出再置為0撼嗓，此時為了防止有的數(shù)出現(xiàn)多次進行了專門的判斷柬采，若該位已經(jīng)為1，則直接加入結(jié)果中(因為兩重復(fù)的數(shù)出現(xiàn)必取其一)且警。然后再進行遍歷粉捻，用flag做標(biāo)識位實現(xiàn)間隔取數(shù)的效果，flag為1則加入res斑芜，隨即flag置0即可跳過下一位肩刃。(當(dāng)然這都是兔子想的==)
代碼：
int arrayPairSum(int* nums, int numsSize) {
int i,j;
int temp;
int sum=0;
int count;
int *p;
int res=0;
p=(int *)malloc(sizeof(int)*20001);
memset(p,0,sizeof(int)*20001);
for(i=0;i<numsSize;i++){
if(p[nums[i]+10000]==0){
p[nums[i]+10000]=1;
}
else {
res+=nums[i];
p[nums[i]+10000]=0;
}
}
int bianli=0;
int flag=1;
for(bianli=0;bianli<20001;bianli++){
if(p[bianli]==1){
if(flag){
res+=bianli-10000;
flag=0;
}
else{
flag=1;
}
}
}
return res;
}
