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

561. Array Partition I

题目链接

561. Array Partition I

题目分析

本题给了一个数组，要求将数组分为n个只有2个元素的一对。
使得每对数字中最小的数加起来的和最大。

思路

首先，需要把数组分为2个一对。用array_chunk即可。

其次，需要取每对数字中最小的那一个数字，用于求和。
因为我们需要最终求和最大，但每组数字中又取最小。
因此，要使每组中最大的数字和最小的数组之差最小，这样才能使“损失”最小。

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

若分为[[1,8],[2,7]]或[[1,7],[2,8]]两组，那么每组取最小后，会得到[1,2]。求和后为3。
当比较大的数字和比较小的数字数字组成一对时，较大的数字都没办法用于求和（因为题目要取每组数字中最小的数）。
当分为[[1,2],[7,8]]两组时，每组取最小后，会得到[1,7]。求和后为8，比3大。

故，先对数组排序，再两两分组，从每组中获取第0个元素参与计算即可。

最终代码

<?php
class Solution {
    function arrayPairSum($nums) {
        sort($nums);
        $a = array_chunk($nums,2);
        return array_sum(array_column($a,0));
    }
}

若觉得本文章对你有用，欢迎用爱发电资助。