每日一练：LeeCode-561、 数组拆分【数组+排序】

给定长度为 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

提示：

• 1 <= n <= 10^4
• nums.length == 2 * n
• -10^4 <= nums[i] <= 10^4

思路

希尔排序

class Solution {
    public int arrayPairSum(int[] nums) {
        nums = ShellSort(nums); // 对输入数组进行希尔排序，使得数组中的元素按照从小到大的顺序排列
        int res = 0; // 初始化最终结果为0
        for(int i = 0; i < nums.length; i++){ // 遍历排序后的数组
            res += nums[i]; // 将数组中的每个元素依次加到结果中
            i++; // 跳过下一个元素，因为数组已经排序，所以取每个配对的第一个元素即可
        }
        return res; // 返回最终结果
    }

    public int[] ShellSort(int[] array) {
        int len = array.length; // 获取数组的长度
        int temp, gap = len / 2; // 初始化临时变量和希尔增量为数组长度的一半
        while (gap > 0) { // 当希尔增量大于0时，执行循环
            for (int i = gap; i < len; i++) { // 对数组中每个元素进行希尔增量排序
                temp = array[i]; // 将当前元素暂存到临时变量中
                int preIndex = i - gap; // 计算当前元素的前一个希尔增量的索引
                // 对当前分组中的元素进行插入排序
                while (preIndex >= 0 && array[preIndex] > temp) { // 当前元素小于前一个元素时，进行插入排序
                    array[preIndex + gap] = array[preIndex]; // 将前一个元素移到当前位置
                    preIndex -= gap; // 更新前一个元素的索引
                }
                array[preIndex + gap] = temp; // 将当前元素插入到正确的位置
            }
            gap /= 2; // 缩小希尔增量，直到增量为1时，整个数组被排序
        }
        return array; // 返回排序后的数组
    }
}

• 首先调用 ShellSort(nums) 方法对输入数组进行希尔排序，使得数组中的元素按照从小到大的顺序排列。
• 然后初始化最终结果 res 为0。
• 通过一个 for 循环遍历排序后的数组，每次取两个元素中较小的那个，将其加到结果 res 中。因为数组已经排序，所以取每个配对的第一个元素即可，所以 i++ 用于跳过下一个元素。
• 最后返回最终结果 res。
• ShellSort(int[] array) 方法实现了希尔排序算法，用于对输入数组进行排序。
• 首先获取数组的长度，并初始化临时变量 temp 和希尔增量 gap 为数组长度的一半。
• 通过一个 while 循环，对数组中的每个元素进行希尔增量排序。
• 在循环中，首先将当前元素暂存到临时变量中，然后计算当前元素的前一个希尔增量的索引，并对当前分组中的元素进行插入排序。
• 在插入排序中，当当前元素小于前一个元素时，将前一个元素移到当前位置，然后更新前一个元素的索引。
• 最后返回排序后的数组。

Arrays.sort()

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