LeetCode 561：數組拆分 I Array Partition I

文章全部來自公衆号：愛寫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:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

提示:

1. n 是正整數,範圍在 [1, 10000].
2. 數組中的元素範圍在 [-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<nums.length;i+=2){
            sum+=nums[i];
        }
        return sum;
    }
}           

擴充：

維基百科上對排序算法介紹的非常詳細，并且進行了歸類比較，位址：

這裡簡單推薦兩個：

• 快速排序 （quick sort）—

  

  期望時間，

  

  最壞情況；對于大的、随機數清單一般相信是最快的已知排序（C語言标準庫的

  qsort()

  排序用的就是快速排序算法，利用遞歸和分而治之思想）
• 桶排序 （bucket sort）—

  

  ；需要

  

  額外空間（典型的犧牲空間換時間）

冒泡排序、選擇排序都是比較簡單容易了解，複雜度是

n^2

,是以不再贅述。