C#LeetCode刷题之#561-数组拆分 I(Array Partition I)
问题
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3718 访问。
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。
输入: [1,4,3,2]
输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
提示:
n 是正整数,范围在 [1, 10000].
数组中的元素范围在 [-10000, 10000].
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].
示例
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3718 访问。
public class Program {
public static void Main(string[] args) {
int[] nums = null;
nums = new int[] { 1, 4, 3, 2 };
var res = ArrayPairSum(nums);
Console.WriteLine(res);
Console.ReadKey();
}
private static int ArrayPairSum(int[] nums) {
Array.Sort(nums);
var sum = 0;
for(int i = 0; i < nums.Length; i += 2) {
sum += nums[i];
}
return sum;
}
}
以上给出1种算法实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3718 访问。
4
分析:
LeetCode 并没有把这题打上贪心标签,我觉得是可以讨论的。我们要解的是所有子数组 min 之后的最大和,这是一种典型的需要贪心思想求解的题目,以局部最优解合并得出整体最优解,所以关键点在于贪心策略的选择。那么对于该题来说贪心策略显然为每个子数组中的2个数的差的绝对值在最小时,整个数组合并出的 min 值最大;否则,若2个数的差的绝对值过大,那么对于整个拆分过后的数组来说,损失了过多的值。也就是说,我们直接排序之后,取出奇(jī)数值相加即可。
显而易见,以上算法的时间复杂度基于 Array.Sort() 所采用的排序算法。
最新文章
- OpenCASCADE Data Exchange - 3D PDF
- Eclipse 安装 Maven 插件(图文解说)
- [转]你不需要jQuery
- Windows Store App 近期访问列表
- [DNX]解决dnu restore时找不到Newtonsoft.Json的问题
- 从OGRE,GAMEPLAY3D,COCOS2D-X看开源
- COB (Chip On Board) 製程介紹/簡介/注意事項 II
- ubuntu12.04 android studio 安装
- Linux实战教学笔记18:linux三剑客之awk精讲
- WannaflyUnion每日一题
- 让asp.net网站支持多语言,使用资源文件
- appium 解锁九宫格
- Python的伪私有属性
- Scikit-learn:模型评估Model evaluation
- Node笔记四
- java学习之—排序
- 【Android】ImageView ScaleType属性值
- bzoj2555: SubString sam+lct
- 小程序 picker 多列选择器 数据动态获取
- 2017-2018 第一学期201623班《程序设计与数据结构》-第5&;6周作业问题总结
热门文章
- svg 使用中的疑惑点
- C++ 深搜调错
- 【软件安装】在 CentOS 7(Linux)上部署流媒体服务(Tengine、ffmpeg、Centos 7、nginx-http-flv-module、OBS)
- 深入探究JVM之内存结构及字符串常量池
- 题解 洛谷 P5303 【[GXOI/GZOI2019]逼死强迫症】
- 题解 洛谷 P4899 【[IOI2018] werewolf 狼人】
- Jupyter Notebook 导出PDF与Latex中文支持
- Nginx实现JWT验证-基于OpenResty实现
- iframe和DataForm
- python匿名函数和内置函数