C#LeetCode刷题之#561-数组拆分 I(Array Partition I)

C#LeetCode刷题之#561-数组拆分 I(Array Partition I)

问题

给定长度为 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).

提示:

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

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.

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

示例

public class Program {

    public static void Main(string[] args) {
        int[] nums = null;

        nums = new int[] { 1, 4, 3, 2 };
        var res = ArrayPairSum(nums);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int ArrayPairSum(int[] nums) {
        Array.Sort(nums);
        var sum = 0;
        for(int i = 0; i < nums.Length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }

}

以上给出1种算法实现,以下是这个案例的输出结果:

4

分析:

LeetCode 并没有把这题打上贪心标签,我觉得是可以讨论的。我们要解的是所有子数组 min 之后的最大和,这是一种典型的需要贪心思想求解的题目,以局部最优解合并得出整体最优解,所以关键点在于贪心策略的选择。那么对于该题来说贪心策略显然为每个子数组中的2个数的差的绝对值在最小时,整个数组合并出的 min 值最大;否则,若2个数的差的绝对值过大,那么对于整个拆分过后的数组来说,损失了过多的值。也就是说,我们直接排序之后,取出奇()数值相加即可。

显而易见,以上算法的时间复杂度基于 Array.Sort() 所采用的排序算法。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3718

发表评论

登录后才能评论