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