题目描述 LeetCode 561

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

中文描述

输入一个数组，然后两两组成一对，在每一对中选择最小的，然后使每一对中最小的组成的和最大。

解题思路

• 思路1：快速排序
  没通过..
  可能是因为递归的原因，外加定位首选第一位，导致时间超过，挂了。。
• 思路2，归并排序
  通过，事实证明归并比快排快。

C 语言代码

• 思路1，快速排序测试用例通过 56/81，在第 57 挂了。。

# include <stdio.h>

void quick_sort(int a[], int left, int right)
{
    int i, j;
    int temp;

    if (left < right)
    {
        i = left;
        j = right;
        temp = a[i];
        
        while ( i < j)
        {
            while(i < j && a[j] >= temp)
            {
                j -- ;
            }
            if( i < j )
            {
                a[i ++ ] = a[j];
            }

            while(i < j && a[i] < temp)
            {
                i ++ ;
            }
            if( i < j )
            {
                a[j -- ] = a[i];
            }
        }
        a[i] = temp;
        quick_sort(a, 0, i - 1);
        quick_sort(a, i + 1, right);
    }
}

int arrayPairSum(int* nums, int numsSize) 
{
    int i, sum = 0;

    quick_sort(nums, 0, numsSize - 1); 
    for (i = 0; i < numsSize; i += 2)
    {
        sum += *(nums + i);
    }

    return sum;
}

main()
{
    int a[10] = {1, 4, 3, 2};
    printf("%d\n\n",arrayPairSum(a, 4));
}

快速排序 挂了

• 思路2， 归并排序，通过。

# include <stdio.h>

//将有二个有序数列a[first...mid]和a[mid...last]合并。  
void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid, n = last;
    int k = 0;

    while(i <= m && j <= n)
    {
        if (a[i] <= a[j])
        {
            temp[k++] = a[i++];
        }
        else
        {
            temp[k++] = a[j++];
        }
    }

    while( i <= m)
    {
        temp[k++] = a[i++];
    }

    while( j <= n)
    {
        temp[k++] = a[j++];
    }
    
    for (i = 0; i < k; i ++)
    {
        a[first + i] = temp[i];
    }
}
    
void mergesort(int a[], int first, int last, int temp[])
{
    int mid = (first + last) / 2;

    if(first < last)
    {
        mergesort(a, first, mid, temp);        // 左边有序
        mergesort(a, mid + 1, last, temp);     // 右边有序
        mergearray(a, first, mid, last, temp); // 再将两个有序数列合并
    }
}

int arrayPairSum(int* nums, int numsSize) 
{
    int i, sum = 0;
    int temp[100];

    mergesort(nums, 0, numsSize - 1, temp); 

    for (i = 0; i < numsSize; i += 2)
    {
        sum += *(nums + i);
    }

    return sum;
}

main()
{
    int a[10] = {1, 4, 3, 2};
    
    printf("%d\n\n",arrayPairSum(a, 4));
}

归并排序运行结果