561. Array Partition I

原题链接

• 题目意思:给定一个长度为2n的数组,分成n组(a1, b1), (a2, b2), …, (an, bn) ,求min(a1, b1)+min(a2, b2)+ …,min(an, bn)的最大值
• 算法证明(出处)

假设每一对i，bi >= ai。
Sm = min(a1, b1) + min(a2, b2) + … + min(an, bn)。鉴于1，Sm = a1 + a2 + … + an。
Sa = a1 + b1 + a2 + b2 + … + an + bn。Sa对于给定的输入是恒定的。
表示di = |ai - bi|。鉴于1，di = bi - ai。表示Sd = d1 + d2 + … + dn。
所以Sa = a1 + a1 + d1 + a2 + a2 + d2 + … + an + an + dn = 2Sm + Sd=> Sm = (Sa - Sd) / 2。为了获得最大值Sm，给定Sa是恒定的，我们需要Sd尽可能小。
因此，这个问题变成了在数组中找到对，使di（ai和之间的距离bi）之和尽可能小。显然，相邻元素的这些距离之和最小。如果这不够直观，请参阅附图。案例1最小Sd。

• 代码巧妙点:
  
  1. 在已知数据的范围(本题是-10000~10000)的情况下,可以用类似标记数组,把(输入数据+10000)当成标记数组下标(避免负数引起的下标<0),在相应位置进行累加,然后遍历标记数组,这样可避免排序,标准的空间换时间
  2. 输入数据可能重复,所以,在遍历标记数组时,每个不为值不为0的位置都要进行循环,循环用个布尔类型变量控制奇数点累加,并让相应标记数组值自减,当数组值为0时循环结束

int arrayPairSum(int* nums, int numsSize) {
   int hashTable[20003]={0};
   for(int i=0;i<numsSize;i++){
       hashTable[nums[i]+10000]++;
   }
    int res=0;
    bool odd=true;
   for(int i=0;i<sizeof(hashTable)/sizeof(hashTable[0]);i++){
       while(hashTable[i]){
           if(odd){
               res+=i-10000;
            }
            odd=!odd;
           hashTable[i]--;
       }
   }
    return res;
}