对数组按需分组

题目

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。

• 示例：

输入: [1,4,3,2]

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4)。

解法

对于示例数组，所有的分组情况为：

// 1.
[1, 4], [2, 3] // 结果为 1 + 2 = 3
// 2.
[1, 3], [2, 4] // 结果为 1 + 2 = 3
// 3.
[1, 2], [3, 4] // 结果为 1 + 3 = 4

然而，当数据过多时，无法直接列举出所有情况。
因此，我们首先可以考虑将数据进行排序。并且，我们知道，min函数的功能即获取较小的数，忽略较大的数。根据以上列举情况可以也看出，最大和的分组方式即为从小到大依次分组。故可以得出结论：

1. 升序排列数组，得到有序数据。
2. 依次间隔获取数据并求和。

NSInteger getMaxSumWithSeparatingArray(NSArray <NSNumber *>* info) {
    // 1. 升序排列
    NSArray *sortedInfo = [info sortedArrayUsingComparator:^NSComparisonResult(NSNumber *obj1, NSNumber *obj2) {
        return [obj1 compare:obj2];
    }];
    
    // 2. 依次对奇数项求和
    NSInteger sum = 0;
    
    NSInteger index = 0;
    while (index < sortedInfo.count) {
        sum += [sortedInfo[index] integerValue];
        index += 2;
    }
    return sum;
}