561.数组拆分

发表于 | 分类于
字数统计: 217 | 阅读时长 ≈ 1

一、题目描述

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

示例 1:

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

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

提示:

  1. n 是正整数,范围在 [1, 10000].
  2. 数组中的元素范围在 [-10000, 10000].

二、题解

  1. 算法描述

    • 排序+最小值累加

  2. 个人分析

    • 首先将给定数组排序，然后每两位选择较小值进行累加

  3. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int min(int a, int b)
    {
        return a > b ? b : a;
    }
    int compare1(const void *a, const void *b)
    { //升序
        return (*(int *)a - *(int *)b);
    }
    int arrayPairSum(int *nums, int numsSize)
    {
        int sizeOfElem = sizeof(nums[0]);
        qsort(nums, numsSize, sizeOfElem, compare1);
        int i, res = 0;
        for (i = 0; i < numsSize; i += 2)
            res += min(nums[i], nums[i + 1]);
        return res;
    }