[leetcode]561. Array Partition I

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

思路：在一个有序数组中，两两之间取最小值才能将损失的差值弥补到最小，使所求得的和最大。因而应先排序再间隔取值求和。

问题：
一开始尝试了最简单的两层for循环排序，之后再间隔取值加和，但是这样超出了运行时间要求。
改变思路，先遍历整个数组，将数组中的值按顺序写入新数组中，未存入时标志为0，存入置为1，取出再置为0，此时为了防止有的数出现多次进行了专门的判断，若该位已经为1，则直接加入结果中(因为两重复的数出现必取其一)。然后再进行遍历，用flag做标识位实现间隔取数的效果，flag为1则加入res，随即flag置0即可跳过下一位。(当然这都是兔子想的==)

代码：

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