LeetCode 561:数组拆分 I Array Partition I
文章全部来自公众号:爱写bug
算法是一个程序的灵魂。
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.
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。
Example 1:
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].
提示:
- n 是正整数,范围在 [1, 10000].
- 数组中的元素范围在 [-10000, 10000].
解题思路:
其实就是把 数组排序,然后按顺序 每两个数既是一对,每对的第一个数累加之和即为所求。就是考一下各类排序算法的性能。
先使用内置 sort()
函数理解一下思路:
Java:
import java.util.Arrays; class Solution { public int arrayPairSum(int[] nums) { Arrays.sort(nums); int sum=0; for (int i=0;i<nums.length;i+=2){ sum+=nums[i]; } return sum; } }
扩展:
维基百科上对排序算法介绍的非常详细,并且进行了归类比较,地址:
这里简单推荐两个:
- 快速排序(quick sort)—期望时间,最坏情况;对于大的、随机数列表一般相信是最快的已知排序(C语言标准库的
qsort()
排序用的就是快速排序算法,利用递归和分而治之思想) - 桶排序(bucket sort)—;需要额外空间(典型的牺牲空间换时间)
冒泡排序、选择排序都是比较简单容易理解,复杂度是 n^2
,所以不再赘述。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Java常见面试题汇总
动力节点Java培训最新上线Java实验班,等你来测试自己适不适合学习Java编程哦!今天的主题我们来谈谈求职,每个程序员的生涯总有几次求职经历,对于求职者而言,在面对自己心仪的公司之前总要做足成分的准备,一份全面精细的面试题可以帮助我们减少很多麻烦,为此动力节点IT培训的小编特地做了Java面试题的文章,一方面可以帮助大家巩固基础,另一方面也希望帮助苦于面试的朋友。 Java中Runnable和Callable有什么不同? Runnable和Callable都代表那些要在不同的线程中执行的任务。Runnable从JDK1.0开始就有了,Callable是在JDK1.5增加的。它们的主要区别是Callable的call()方法可以返回值和抛出异常,而Runnable的run()方法没有这些功能。Callable可以返回装载有计算结果的Future对象。 接口:Collection Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不...
- 下一篇
玩转阿里云函数计算(三)——一键配置 SpringBoot 应用
前言 阿里云函数计算 Function Compute(FC),旨在帮助用户采用弹性伸缩、动态分配资源的方式,来执行业务函数。让用户无需购买部署服务器,无需考虑业务负载,就能快速搭建可处理高并发的后台服务。函数计算平台针对 Java 语言推出的 Java HTTP 触发器功能,能够无缝迁移传统的 Java Web 应用。支持基于 Servlet 协议的 Web 框架所开发的应用,比如常用的 Spring、SpringBoot、Struts2等。 本文介绍如何使用 Java HTTP 触发器来快速迁移 SpringBoot 应用 demo-springboot-hello,并使用函数计算提供的 fun 工具 来快速部署。 继续本文之前,建议先阅读 玩转阿里云函数计算(一)——Java Http 触发器极速迁移传统 Spring 应用 玩转阿里
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS关闭SELinux安全模块
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- Hadoop3单机部署,实现最简伪集群
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS6,CentOS7官方镜像安装Oracle11G
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8编译安装MySQL8.0.19
- CentOS6,7,8上安装Nginx,支持https2.0的开启