IOS 算法(基础篇) ----- 数组拆分 I

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

例子:

输入
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

输入
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

思路:

题意不算难理解, 数组拆分成一对对, 然后取每一对中最小值, 找最小值相加最大的和

看例子也可以看出, 我们需要尽可能的大数大数放一起, 小数小数放一起, 因为一大一小, 大数会被浪费
那么最优就是我们将数组正序排序, 然后依次取偶数项求和即可

按照题意我们可以机械翻译得

代码:

未翻译版

    func arrayPairSum(_ nums: [Int]) -> Int {
        
        var temp = nums.sorted(), index = 0, result = 0
        while index < temp.count {
            result += temp[index]
            index += 2   
        }
        return result

    }

翻译版

    func arrayPairSum(_ nums: [Int]) -> Int {
        
        // 数组正序排序, index为数组下标, result为结果
        var temp = nums.sorted(), index = 0, result = 0

        // 循环 index = temp.count结束, 不能数组越界
        while index < temp.count {

            // 依次 每次取 temp[index], temp[index+1]最小值, 因为我们是正序排列, 最小值肯定为 temp[index]
            result += temp[index]
            
            // 这块写成这种也可以, 便于理解
            // result += min(temp[index], temp[index+1])

            // 因为每次取2个, 所以下次 index = index + 2
            index += 2   
        }
        // 最后得到的result就是我们找的结果
        return result
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址