【算法千题案例】每日一练 LeetCode打卡——106.数组拆分 I

呆呆敲代码的小Y

发布于 2022-01-24 10:16:50

1940

发布于 2022-01-24 10:16:50

文章被收录于专栏：呆呆敲代码的小Y 公众号呆呆敲代码的小Y 公众号

前言
- 原题样例：数组拆分 I
  - C#方法：排序
  - Java 方法：排序
- 总结

前言

算法题

每天打卡一道算法题，既是一个学习过程，又是一个分享的过程
提示：本专栏解题编程语言一律使用 C# 和 Java 两种进行解题
要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧！
今天是力扣算法题持续打卡第101天！

算法题

原题样例：数组拆分 I

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

示例3:

输入：name = "leelee", typed = "lleeelee"
输出：true

提示：

1 <= n <= 104
nums.length == 2 * n
-104 <= nums[i] <= 104

C#方法：排序

根据题意得知最终结果是最小值累加起来，但是我们的最大值永远只能被排除。

所以此题的核心就是将第二大的值累加起来得出结果即可~

代码：

public class Solution {
    public int ArrayPairSum(int[] nums) {
        Array.Sort(nums);
        int ret = 0;
        for(int i =0;i<nums.Length;i=i+2)
        {
            ret += nums[i];
        }
        return ret;
    }
}

执行结果

通过
执行用时：136 ms，在所有 C# 提交中击败了66.14%的用户
内存消耗：48.9 MB，在所有 C# 提交中击败了51.70%的用户

Java 方法：排序

思路解析 先进行排序，假设排完序的结果为a1<=b1<=a2<=b2<=…<=an<=bn

a1作为全局最小值，无论跟谁一组a1都会被累加进答案，相反，a1的搭档会被永久排除。
既然如此，莫不如排除一个较小的数，即给a1找一个“最小的搭档”b1。
当a1、b1被处理之后，a2同理分析。
所以，最终选择a1,a2,…,an会得到最好的结果。

代码：

class Solution {
    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;
    }
}

执行结果

通过
执行用时：12 ms，在所有 Java  提交中击败了97.41%的用户
内存消耗：40.4 MB，在所有 Java 提交中击败了16.53%的用户

复杂度分析

时间复杂度：O( nlogn)
空间复杂度：O(logn)

总结

今天是力扣算法题打卡的第106天！
文章采用 C#和 Java 两种编程语言进行解题
一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
那今天的算法题分享到此结束啦，明天再见！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022/01/24 ，如有侵权请联系 cloudcommunity@tencent.com 删除

java

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

java

编程算法

登录后参与评论

0 条评论

热度

【算法千题案例】每日一练 LeetCode打卡——106.数组拆分 I

【算法千题案例】每日一练 LeetCode打卡——106.数组拆分 I

前言

原题样例：数组拆分 I

C#方法：排序

Java 方法：排序

总结

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐