LeetCode 561：數組拆分 I Array Partition I

wangtdgoodluck 發布于2019-07-31 11:25 / 3107人閱讀

摘要：給定長度為的數組你的任務是將這些數分成對例如，使得從到的總和最大。提示是正整數范圍在數組中的元素范圍在解題思路其實就是把數組排序，然后按順序每兩個數既是一對，每對的第一個數累加之和即為所求。就是考一下各類排序算法的性能。

文章全部來自公眾號：愛寫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多維數組的拆分

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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