LeetCode 561：数组拆分 I Array Partition I

wangtdgoodluck 发布于2019-07-31 11:25 / 3106人阅读

摘要：给定长度为的数组你的任务是将这些数分成对例如，使得从到的总和最大。提示是正整数范围在数组中的元素范围在解题思路其实就是把数组排序，然后按顺序每两个数既是一对，每对的第一个数累加之和即为所求。就是考一下各类排序算法的性能。

文章全部来自公众号：爱写bug

算法是一个程序的灵魂。
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) ，使得从1 到 n 的 min(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 是正整数,范围在 [1, 10000].

数组中的元素范围在 [-10000, 10000].

解题思路：

其实就是把数组排序，然后按顺序每两个数既是一对，每对的第一个数累加之和即为所求。就是考一下各类排序算法的性能。

先使用内置 sort() 函数理解一下思路：

Java：

import java.util.Arrays;
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum=0;
        for (int i=0;i
扩展：
维基百科上对排序算法介绍的非常详细，并且进行了归类比较，地址： https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
这里简单推荐两个：


快速排序（quick sort）—期望时间，最坏情况；对于大的、随机数列表一般相信是最快的已知排序（C语言标准库的qsort()排序用的就是快速排序算法，利用递归和分而治之思想）

桶排序（bucket sort）—；需要额外空间（典型的牺牲空间换时间）

冒泡排序、选择排序都是比较简单容易理解，复杂度是 n^2 ,所以不再赘述。

GPU云服务器云服务器 php字符拆分数组 php 数组平均拆分数组array php多维数组的拆分

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/45090.html

LeetCode 561：数组拆分 I Array Partition I

摘要：给定长度为的数组你的任务是将这些数分成对例如，使得从到的总和最大。提示是正整数范围在数组中的元素范围在解题思路其实就是把数组排序，然后按顺序每两个数既是一对，每对的第一个数累加之和即为所求。就是考一下各类排序算法的性能。文章全部来自公众号：爱写bug 算法是一个程序的灵魂。Given an array of 2n integers, your task is to group the...

gnehc 2019-08-16 18:28 评论0 收藏0
Leetcode PHP题解--D14 561. Array Partition I

摘要：题目链接题目分析本题给了一个数组，要求将数组分为个只有个元素的一对。因此，要使每组中最大的数字和最小的数组之差最小，这样才能使损失最小。当分为两组时，每组取最小后，会得到。求和后为，比大。 561. Array Partition I 题目链接 561. Array Partition I 题目分析本题给了一个数组，要求将数组分为n个只有2个元素的一对。使得每对数字中最小的数加起...

stonezhu 2019-07-01 12:36 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
一些前端算法詳解 --- (不定时更新)

摘要：也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因於年提出而得名。前言因為比较随心所欲,所以我不按难度分享算法,所以你们会看到有时候顺序有变化,因為我发表的时候会按照难度修改下位置,尽量让你们看的时候能从简单开始,以后每次更新都加个更新时间好了,让你们知道我进度.新增计时函数直观对比效率并且因為资料比较杂,很多都是我个人理解说法,如果有发...

Baaaan 2019-08-26 10:35 评论0 收藏0
[Leetcode - Dynamic Programming] Partition Equal S

摘要：背包问题假设有个宝石，只有一个容量为的背包，且第个宝石所对应的重量和价值为和求装哪些宝石可以获得最大的价值收益思路我们将个宝石进行编号，寻找的状态和状态转移方程。我们用表示将前个宝石装到剩余容量为的背包中，那么久很容易得到状态转移方程了。 Partition Equal Subset Sum Given a non-empty array containing only posi...

qpal 2019-08-14 16:41 评论0 收藏0