排序算法之數組拆分

題目

給定長度為 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傑少