Leetcode PHP題解--D14 561. Array Partition I

stonezhu 發(fā)布于2019-07-01 12:36 / 2086人閱讀

摘要：題目鏈接題目分析本題給了一個(gè)數(shù)組，要求將數(shù)組分為個(gè)只有個(gè)元素的一對(duì)。因此，要使每組中最大的數(shù)字和最小的數(shù)組之差最小，這樣才能使損失最小。當(dāng)分為兩組時(shí)，每組取最小后，會(huì)得到。求和后為，比大。

561. Array Partition I 題目鏈接

561. Array Partition I

題目分析

本題給了一個(gè)數(shù)組，要求將數(shù)組分為n個(gè)只有2個(gè)元素的一對(duì)。
使得每對(duì)數(shù)字中最小的數(shù)加起來(lái)的和最大。

思路

首先，需要把數(shù)組分為2個(gè)一對(duì)。用array_chunk即可。

其次，需要取每對(duì)數(shù)字中最小的那一個(gè)數(shù)字，用于求和。
因?yàn)槲覀冃枰罱K求和最大，但每組數(shù)字中又取最小。
因此，要使每組中最大的數(shù)字和最小的數(shù)組之差最小，這樣才能使“損失”最小。

例如，[1,2,7,8]。

若分為[[1,8],[2,7]]或[[1,7],[2,8]]兩組，那么每組取最小后，會(huì)得到[1,2]。求和后為3。
當(dāng)比較大的數(shù)字和比較小的數(shù)字?jǐn)?shù)字組成一對(duì)時(shí)，較大的數(shù)字都沒(méi)辦法用于求和（因?yàn)轭}目要取每組數(shù)字中最小的數(shù)）。
當(dāng)分為[[1,2],[7,8]]兩組時(shí)，每組取最小后，會(huì)得到[1,7]。求和后為8，比3大。

故，先對(duì)數(shù)組排序，再兩兩分組，從每組中獲取第0個(gè)元素參與計(jì)算即可。

最終代碼

若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/31081.html

相關(guān)文章

LeetCode 561：數(shù)組拆分 I Array Partition I

摘要：給定長(zhǎng)度為的數(shù)組你的任務(wù)是將這些數(shù)分成對(duì)例如，使得從到的總和最大。提示是正整數(shù)范圍在數(shù)組中的元素范圍在解題思路其實(shí)就是把數(shù)組排序，然后按順序每?jī)蓚€(gè)數(shù)既是一對(duì)，每對(duì)的第一個(gè)數(shù)累加之和即為所求。就是考一下各類排序算法的性能。文章全部來(lái)自公眾號(hào)：愛寫bug 算法是一個(gè)程序的靈魂。Given an array of 2n integers, your task is to group the...

gnehc 2019-08-16 18:28 評(píng)論0 收藏0
LeetCode 561：數(shù)組拆分 I Array Partition I

摘要：給定長(zhǎng)度為的數(shù)組你的任務(wù)是將這些數(shù)分成對(duì)例如，使得從到的總和最大。提示是正整數(shù)范圍在數(shù)組中的元素范圍在解題思路其實(shí)就是把數(shù)組排序，然后按順序每?jī)蓚€(gè)數(shù)既是一對(duì)，每對(duì)的第一個(gè)數(shù)累加之和即為所求。就是考一下各類排序算法的性能。文章全部來(lái)自公眾號(hào)：愛寫bug 算法是一個(gè)程序的靈魂。Given an array of 2n integers, your task is to group the...

wangtdgoodluck 2019-07-31 11:25 評(píng)論0 收藏0
Leetcode PHP題解--D48 985. Sum of Even Numbers After

摘要：結(jié)果中第個(gè)元素的結(jié)果為，當(dāng)執(zhí)行第步時(shí)，數(shù)組中偶數(shù)元素的和。再在每一步計(jì)算的過(guò)程中，判斷當(dāng)前位置是否為偶數(shù)。是則加進(jìn)偶數(shù)和中。把每一步的偶數(shù)和記錄下來(lái)，以便最后返回。 D48 985. Sum of Even Numbers After Queries 題目鏈接 985. Sum of Even Numbers After Queries 題目分析給定一個(gè)初始數(shù)組A，再給定一個(gè)二維操作...

yacheng 2019-07-01 12:44 評(píng)論0 收藏0
Leetcode PHP題解--D16 922. Sort Array By Parity II

摘要：題目鏈接題目分析給定一個(gè)整數(shù)數(shù)組，使數(shù)組中偶數(shù)位的值為偶數(shù)，奇數(shù)位的值為奇數(shù)。例如，，是偶數(shù)，所以要為偶數(shù)。，是奇數(shù)，所以要為奇數(shù)。思路用拆分?jǐn)?shù)組中的偶數(shù)和奇數(shù)，再輪流塞進(jìn)新數(shù)組中。最終代碼若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。 922. Sort Array By Parity II 題目鏈接 922. Sort Array By Parity II 題目分析給定一個(gè)整數(shù)數(shù)組A，...

hosition 2019-07-01 12:37 評(píng)論0 收藏0
Leetcode PHP題解--D66 896. Monotonic Array

摘要：題目鏈接題目分析給定一個(gè)數(shù)字?jǐn)?shù)組，判斷是否單調(diào)遞增或遞減。判斷后，再逐個(gè)遍歷。若為單調(diào)遞減，則不能出現(xiàn)大于前一個(gè)數(shù)組的值。最終代碼若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。 D66 896. Monotonic Array 題目鏈接 896. Monotonic Array 題目分析給定一個(gè)數(shù)字?jǐn)?shù)組，判斷是否單調(diào)遞增或遞減。單調(diào)遞增即,對(duì)于第n位數(shù)字，其后面的數(shù)組都大于或等于它。 ...

henry14 2019-07-01 12:48 評(píng)論0 收藏0