【LeetCode】数组拆分 Java 题解
题目
给定长度为 2n 的整数数组 nums ,你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
代码
复制代码
总结
上述代码的时间复杂度是 O(n log(n))
解题的代码比较简洁,主要应用了贪心的思想。
贪心算法在有最优子结构的问题中尤为有效。
贪心算法有两种证明方法:反证法和归纳法。一般情况下,一道题只会用到其中的一种方法来证明。
反证法:如果交换方案中任意两个元素/相邻的两个元素后,答案不会变得更好,那么可以推定目前的解已经是最优解了。
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/e89a8adfb92e0b9812f692a67】。文章转载请联系作者。
评论