美文网首页前端算法让前端飞程序员
跟我一起刷leetCode算法题3之Array Partitio

跟我一起刷leetCode算法题3之Array Partitio

作者: 打铁大师 | 来源:发表于2017-07-29 19:20 被阅读56次

    561.Array Partition I

    这是leetCode第561题,难度Easy

    题目

    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.

    意思是:给出一个2n个整数的数组,你的任务是将这些整数分组为n对整数,如(a1,b1),(a2,b2),...(an,bn)从而在i为1到n的时候,使(ai,bi)最小值的总和尽可能得大

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

    思路:

    要把n组整数的最小值的和,尽可能大。就意味着,要尽可能的把大一些的值分在一组,小一点的值分在一组,这样得到n个最小值的时候,大一点的数字就多,小一点的数字就小,结果就尽可能大。
    因此,我们需要对数组进行排序,从小到大排序。从数组索引位置0开始,俩俩为一组。那么每组最小值的索引就是0,2,4,...

    代码如下:

    var arrayPairSum = function (nums) {
        var l = nums.length;
        var sum = 0;
        //对数组进行排序,从小到大排
        nums.sort(function (a, b) {
            if (a < b) {
                return -1;
            } else {
                return 1;
            }
        });
        for (var i = 0; i < l; i += 2) {
            //每一组的最小值,索引都是偶数
            sum += nums[i];
        }
          return sum;
     };

    相关文章

      网友评论

        本文标题:跟我一起刷leetCode算法题3之Array Partitio

        本文链接:https://www.haomeiwen.com/subject/lxpclxtx.html