专业的JAVA编程教程与资源

网站首页 > java教程 正文

「LeetCode」数组拆分Java题解

temp10 2024-11-18 17:04:55 java教程 12 ℃ 0 评论

题目

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

返回该 最大总和 。

「LeetCode」数组拆分Java题解

代码

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))

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

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

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

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

本文暂时没有评论,来添加一个吧(●'◡'●)

欢迎 发表评论:

最近发表
标签列表