Go语言题解LeetCode561数组拆分
作者:刘09k11 发布时间:2023-06-20 22:49:14
一 描述
561. 数组拆分 I - 力扣(LeetCode) (leetcode-cn.com)
给定长度为 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
提示:
1 <= n <= 10^4
nums.length == 2 * n
-10^4 <= nums[i] <= 10^4
二 分析
本质思路是将整个队列按从小到大的方式排序,然后从两个相近的数中选取出最小的,取和。使用冒泡法会超出计算时间,因为选用额外增加数组,将大小作为两个数组的下角标,从而进行排序。
三 答案
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
/*
int arr[nums.size()]={0};
int temp=0;
for(int i=0;i<nums.size();i++)
arr[i]=nums[i];
for(int i=0;i<nums.size()-1;i++)
{
for(int j=i+1;j<nums.size();j++)
if(arr[i]>arr[j]) {temp=arr[i];arr[i]=arr[j];arr[j]=temp;} //冒泡排序会超出时间限制
}
int res=0;
for(int i=0;i<nums.size();i+=2){res+=arr[i];}
return res;*/
int n[20001]={0},i=0,j=0,sum=0;
for(i=0;i<nums.size();i++)
n[nums[i]+10000]++; //变相将nums按顺序大小排好,并将顺序存储在n[i]中
for(i=0;i<20001;)
{
if(n[i])
{
if(j%2==0) sum+=i-10000; //按照n[i]中存储的顺序,求得nums[i]
j++; //只有n[i]中有数时,即nums存在这个数时,j才增加,将j变为下角标
n[i]--; //此步防止nums中含有两个相同的数
}
else i++;
}
return sum;
}
};
Python 语言 - 数组拆分
解题思路
排序
今天的题目意思为:把输入的数组拆成 nn 对,将每一对的最小值求和,得到的结果最大。
从题目给出的示例入手分析:
对于示例二 [6,2,6,5,1,2] :
题目给出了最优分法是 (2, 1), (2, 5), (6, 6),min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9。
假如我们换一种分法:(2, 6), (2, 5), (1, 6),min(2, 6) + min(2, 5) + min(1, 6) = 2 + 2 + 1 = 5,则得到的最终结果会变小。
可以看出小数字组成一对、大数字组成一对,每对取 minmin 之后,求和得到的结果才是最大的。
因此,思路就是对输入的数组 numsnums 进行排序,然后依次求相邻的两个元素的最小值,总和就是结果。
代码一
一种各种语言都比较通用的写法是下面这样,用 Python 作为示例:
class Solution(object):
def arrayPairSum(self, nums):
nums.sort()
res = 0
for i in range(0, len(nums), 2):
res += min(nums[i], nums[i + 1])
return res
时间复杂度:O(N * log(N)),超过了 31% 的提交。
空间复杂度:O(1)。
代码二
对于 Python 而言,我们可以用切片操作,把代码简化为:
class Solution(object):
def arrayPairSum(self, nums):
nums.sort()
return sum(nums[::2])
时间复杂度:O(N * log(N)),超过了 100% 的提交,可见切片比 for 循环更快。
空间复杂度:O(N),切片操作产生了新的数组,占用了空间。
代码三
对于 Python 而言,上面的代码二还能继续精简到一行。由于 nums.sort() 是原地操作、没有返回值,所以我们需要用 sorted(nums) 函数返回一个新数组,我们才能在返回结果的基础上继续进行切片。
class Solution(object):
def arrayPairSum(self, nums):
return sum(sorted(nums)[::2])
时间复杂度:O(N * log(N)),超过了 63% 的提交,比方法二更慢。应该是 sorted() 函数拷贝了数组导致。
空间复杂度:O(N),sorted() 函数和切片操作产生了新的数组,占用了空间。
刷题心得
Easy 题经常从示例入手,分析解法。
本题练习了 Python 的切片操作,也练习了两种排序函数的写法。
来源:https://juejin.cn/post/7177383013104238647
猜你喜欢
- 下面这个函数使用FSO对象来判断服务器上的某个文件是否存在:<%Private Function Dir(byVa
- 设计是简单的如果你知道要放的东西该放到哪。曾经在某个电子杂志里看到一篇关于如何在平面设计中偷懒的文章,引发了我的一些思考,在平面设计中有这么
- 以下函数采用FSO对象,文件位置在FSO.ASP。FSO对象的文件编码属性只有三种,系统默认,Unicode,ASCII,并没有我们要的ut
- 以下插件是我在项目中经常使用的jQuery插件,不见得是最好的,但是我目前接触到的jQuery插件中最适合我的。01. jQuery.Fle
- 常用Mysql查询语句记录一、授权1.授权本地用户对所有数据库具有所有权限> grant all privileges on
- 一些很实用且必用的js小脚本代码:脚本1:进入页面后自动播放音乐或其它声音文件<embed src="音乐地址&q
- 阅读上一篇:浏览器中的内存泄露 4.内存泄露的解决方案显式类型转换 首先说说最容易处理的情况 对于类型转换造成的错误,我们可以通过显式类型转
- 查询语言通过在查询表格中键入单词或短语,然后单击按钮执行查询,就可以在 Web 站点中搜索任意的单词或短语(例如,查询表格示例
- 我们一般采用photoshop等做图工具制作电视扫描线效果图片:首先做一个黑白相间的图案,然后用这个图案进行填充,再调整图层的模式或者透明度
- 最近在做文章页盖楼显示的项目,数据来源是跟贴系统生成的UTF8格式的JSON数据。文章页的HTML编码格式是GB2312,在javascri
- 背景:pony是公司的首席体验官、首席产品经理。这次在产品峰会上pony将自己平时经验的积累与大家交流,体验较细。这次分享研发管理部,设计中
- Hi, 大家好~ 好久没有发有营养的东西,今天就扔一篇最近热点的Google Chrome 浏览器的试用心得吧。先说个比较搞的事情,Goog
- MySQL、SQL Server和mSQL都是绝佳的SQL工具,可惜,在ASP的环境下你却用不着它们来创建实用的SQL语句。不过,你可以利用
- 问:SQL Server应该怎样访问Sybase数据库的表?答:具体方法如下:1: 安装Sybase客户端版本的要求:Sybase Clie
- 以前在网上看到的最简单的拖动对象的代码,忘记作者叫什么了。原始代码在IE下有些小问题,并且声明了文档类型为xhtml 1.0后,在FF等非I
- 字符函数——返回字符值这些函数全都接收的是字符族类型的参数(CHR除外)并且返回字符值.除了特别说明的之外,这些函数大部分返回VARCHAR
- 以前在工作中遇到一个问题,当表单发送的数据量很大时,就会报错。查阅MSDN了解到,原因是微软对用Request.Form()可接收的最大数据
- 首先是最常规的方法:<p id="para" title="cssrain demo!" on
- 最近常有厦门的客户通过网站上的联系方式加我QQ,询问网站改版的情况。几乎每日都要针对客户网站存在的问题做一番分析,然后客户以价格等其他因素结
- 这里其实并不需要其它的什么函数来支持,只需要使用MYSQL提供的一些SQL语句就可以了。这里为了简单起见,以MYSQL的系统表USER为例,