写点什么

【LeetCode】数组拆分 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 02 月 16 日

题目

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


返回该 最大总和 。


代码

public class DayCode {    public static void main(String[] args) {        int[] nums = new int[]{1,1,0,1,1,1};        Integer ans = new DayCode().arrayPairSum(nums);        System.out.println("ans is " + ans);    }
/** * https://leetcode-cn.com/problems/array-partition-i/ * @param nums * @return */ public int arrayPairSum(int[] nums) { Arrays.sort(nums); int ans = 0; for (int i = 0; i < nums.length; i += 2) { ans += nums[i]; } return ans; }}
复制代码

总结

  • 上述代码的时间复杂度是 O(n log(n))

  • 解题的代码比较简洁,主要应用了贪心的思想。

  • 贪心算法在有最优子结构的问题中尤为有效。

  • 贪心算法有两种证明方法:反证法和归纳法。一般情况下,一道题只会用到其中的一种方法来证明。

  • 反证法:如果交换方案中任意两个元素/相邻的两个元素后,答案不会变得更好,那么可以推定目前的解已经是最优解了。


发布于: 2021 年 02 月 16 日阅读数: 9
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】数组拆分Java题解