排序算法之数组拆分

题目

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

示例1：

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

示例2：

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

解题思路

由于题目需要求得这些组队数字 min 的总和最大，就得减少这些相邻数字的差距。所以，先通过对数组进行一个排序，就可以让相邻数字之间的差距最小。

然后依次求相邻的两个元素的最小值，总和就是最大值。

代码实现

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

复杂度分析

• 时间复杂度：O(nlogn)，即为对数组 nums 进行排序的时间复杂度。
• 空间复杂度：O(logn)，即为排序需要使用的栈空间。

我是杰少，如果您觉的我写的不错，那请给我 点赞+评论+收藏 后再走哦！

往期文章：

• ​​# UE4：来为我们的角色制作一个血条吧​​
• ​​使用 Google Breakpad 来助力解决程序崩溃​​
• ​​UE4 多人游戏服务器探索​​
• ​​使用虚幻引擎自动化工具实现自动化部署​​
• ​​如何在 UE4 中制作一扇自动开启的大门​​
• ​​如何在 UE4 中用代码去控制角色移动​​
• ​​如何给 UE4 场景添加游戏角色​​
• ​​UE4：Android 平台开发实践指南​​
• ​​UE4 开发避坑指南（持续更新）​​
• ​​新年开工啦，放个小烟花庆祝一下​​
• ​​聊聊与苹果审核员的爱恨情仇(下)​​
• ​​聊聊与苹果审核员的爱恨情仇(上)​​
• ​​一名普通工具人的 2021 | 2021年终总结​​
• ​​二叉树刷题总结：二叉搜索树的属性​​
• ​​二叉树总结：二叉树的属性​​
• ​​二叉树总结：二叉树的修改与构造​​
• ​​StoreKit2 有这么香？嗯，我试过了，真香​​
• ​​看完这篇文章，再也不怕面试官问我如何构造二叉树啦！​​
• ​​那帮做游戏的又想让大家氪金，太坏了！​​
• ​​手把手带你撸一个网易云音乐首页 | 适配篇​​
• ​​手把手带你撸一个网易云音乐首页（三）​​
• ​​手把手带你撸一个网易云音乐首页（二）​​
• ​​手把手带你撸一个网易云音乐首页（一）​​
• ​​代码要写注释吗？写你就输了​​
• ​​Codable发布这么久我就不学，摸鱼爽歪歪，哎~就是玩儿​​
• ​​iOS 优雅的处理网络数据，你真的会吗？不如看看这篇​​
• ​​UICollectionView 自定义布局！看这篇就够了​​

1. 关注公众号--- HelloWorld杰少