Array Partition I （数组分隔两两最小值中Sum最大值）

爱被打了一巴掌 2022-03-31 02:21 121阅读 0赞

LeetCode 561. Array Partition I （数组分隔之一）

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:

1.  n is a positive integer, which is in the range of \[1, 10000\].
2.  All the integers in the array will be in the range of \[-10000, 10000\].

--------------------

题目标签：Array

这道题目给了我们一个数组有2n integers， 需要我们把这个数组分成n对，然后从每一对里面拿小的那个数字，把所有的加起来，返回这个sum。并且要使这个sum 尽量最大。如何让sum 最大化呢，我们想一下，如果是两个数字，一个很小，一个很大，这样的话，取一个小的数字，就浪费了那个大的数字。所以我们要使每一对的两个数字尽可能接近。我们先把nums sort 一下，让它从小到大排列，接着每次把index： 0， 2， 4...偶数位的数字加起来就可以了。

public class Solution 
    {
        public int arrayPairSum(int[] nums) 
        {
            int sum = 0;
            
            Arrays.sort(nums);
            
            for(int i=0; i<nums.length; i+=2)
                sum += nums[i];
            
            return sum;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，121人围观）

还没有评论，来说两句吧...

相关阅读

相关获取数组中的最大值,以及最小值

package com.java; import org.junit.Test; import java.util.Arrays;

谁践踏了优雅/ 2023年06月19日 04:29/ 0 赞/ 12 阅读

相关 Java数组中查找最大值和最小值

//从控制台接受10个整数，求出其中的最大值和最小值。 Scanner sc = new Scanner(System.in);

Dear 丶/ 2022年12月16日 06:55/ 0 赞/ 229 阅读

相关 java二维数组中找最大值和最小值_2d数组java中的最小值和最大值

我想输出二维数组的最大值和最小值。Max可以很好地工作，但是即使在数组中没有零的情况下min也总是输出零Math.random()。在本例中，我设置为99以防止较小的机会在数组

灰太狼/ 2022年11月06日 13:55/ 0 赞/ 250 阅读

相关求数组最大值最小值

include <iostream> include <algorithm> using namespace std; in

古城微笑少年丶/ 2022年09月12日 01:44/ 0 赞/ 311 阅读

相关 JavaScript获取数组最大值和最小值

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xht

桃扇骨/ 2022年08月10日 09:54/ 0 赞/ 298 阅读

相关 leetcode 561. Array Partition I 数组元素分组的最小值的和的最大值+直接排序即可

Given an array of 2n integers, your task is to group these integers into n pairs of inte

ゞ浴缸里的玫瑰/ 2022年06月03日 04:16/ 0 赞/ 107 阅读

相关 js获取数组中的最大值最小值

1、遍历方法： var tmp=\[1,12,8,5\]; var max=tmp\[0\]; for(var i=1;i<tmp.length;i++)\{ if(m

川长思鸟来/ 2022年05月31日 02:27/ 0 赞/ 300 阅读

相关在数组中取出最大最小值

利用apply方法 apply用法允许你在某些本来需要写成遍历数组变量的任务中使用内建的函数。例如：找出一个数组中的最大/最小值。 var numbers

忘是亡心i/ 2022年05月28日 05:47/ 0 赞/ 223 阅读

相关 JavaScript 查找数组中最小值和最大值

查找最小值方法1. Math.min.apply(Math,arr) function min(target){ return Math.m

╰+哭是因爲堅強的太久メ/ 2022年05月14日 09:12/ 0 赞/ 290 阅读

相关 Array Partition I （数组分隔两两最小值中Sum最大值）

LeetCode 561. Array Partition I （数组分隔之一） Given an array of 2n integers, your task is to

爱被打了一巴掌/ 2022年03月31日 02:21/ 0 赞/ 122 阅读