LeetCode 0561. 数组拆分
创始人
2025-05-28 05:05:54

【LetMeFly】561.数组拆分 I

力扣题目链接：https://leetcode.cn/problems/array-partition-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

 

提示：

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

方法一：排序

我们先研究一个整数队(a,b)(a, b)(a,b)，假设里面较小的是aaa，那么无论bbb多大，累加到答案中的就只是aaa

因此，我们构造(a,b)(a, b)(a,b)时，使这两个元素之差尽可能地小，才能尽可能地“不浪费”较大的bbb

那么方法就出来了，直接对原始数组排个序，相邻元素两两成对即可。

  • 时间复杂度O(len(nums)×log⁡len(nums))O(len(nums)\times \log len(nums))O(len(nums)×loglen(nums))
  • 空间复杂度O(log⁡len(nums))O(\log len(nums))O(loglen(nums))

时空复杂度的来源主要是排序

AC代码

C++

class Solution {
public:int arrayPairSum(vector& nums) {sort(nums.begin(), nums.end());int ans = 0;for (int i = 0; i < nums.size(); i += 2) {ans += nums[i];}return ans;}
};

Python

class Solution:def arrayPairSum(self, nums: List[int]) -> int:nums.sort()ans = 0for i in range(0, len(nums), 2):ans += nums[i]return ans

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/129548105

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：Pandas数据分析实战练习

下一篇：超实用, 用CSS实现多行文本溢出

相关内容

热门资讯

功率放大器的阻抗匹配原理 　　设计电路的时候，经常会有很多人对于阻抗有疑问，那么什么是阻抗...
苹果xs和xr的区别,ipho... 苹果xs和xr的区别目录苹果xs和xr的区别iphonexr和xs区别苹果xr怎么更新苹果xs和xr...
建设银行个人网上银行怎么登录,... 建设银行个人网上银行怎么登录目录建设银行个人网上银行怎么登录中国建设银行个人网上银行怎么登陆建设银行...
飞机上可以带几条烟,乘飞机可以... 飞机上可以带几条烟目录飞机上可以带几条烟乘飞机可以带多少条烟坐飞机可以带几条烟坐飞机可以带几条烟？飞...
4厘的利息怎么算,银行说四厘的... 4厘的利息怎么算目录4厘的利息怎么算银行说四厘的利息，怎么算？4厘的利息怎么算4厘的利息怎么算 ...
pkg打包node项目到lin... 首先看一下pkg的一些基本操作 pkg打包node项目为exe_node静态项目 导出exe_疆~的...
实验二 Wireshark 报... 实验 Wireshark 报文捕捉分析实验 小组成员：杨某 王某 郭某 徐某 一、实验目的 掌握 W...
RC4加密——python实现... 1.RC4算法简介 ​ RC4算法由Ron rivest于1987年设计出的一种对称加密算法...
跑跑卡丁车怎么反向集气,跑跑卡... 跑跑卡丁车怎么反向集气目录跑跑卡丁车怎么反向集气跑跑卡丁车反向集气教程现代跑跑卡丁车反向补气怎么玩跑...
不做老好人给你们一个最真实的大... 今天给各位分享不做老好人给你们一个最真实的大众T-ROC测评的知识，其中也会对进行解释，如果能碰巧解...
用声音控制跳跃的游戏,别停下八... 用声音控制跳跃的游戏目录用声音控制跳跃的游戏别停下八分音符酱声控技巧分享一个游戏要用尖叫声玩音符游戏...
我国的最高国家权力机关是哪个,... 我国的最高国家权力机关是哪个目录我国的最高国家权力机关是哪个我国的最高国家权力机关是（）。我国最高的...
项目管理（PMP）精选题精讲 请点击↑关注、收藏，本博客免费为你获取精彩知识分享！有惊喜哟࿰...
《伤寒论》——辨太阳病脉证并治... 辨太阳病脉证并治（下）1.问曰：病有结胸①，...
Chat GPT介绍 一、Chat GPT是什么？ ChatGPT是一个基于大规模预训练语言模型的对话系统&...
杨永信被判刑了吗,杨永信被判刑... 杨永信被判刑了吗目录杨永信被判刑了吗杨永信被判刑了吗？杨永信这种禽兽不如的东西为什么还没死没被判罪？...
工程管理硕士要考哪些科目 极速... 工程管理硕士要考哪些科目目录工程管理硕士要考哪些科目工程管理硕士要考哪些科目 工程管理硕士考试...
请神容易送神难下一句是什么,请... 请神容易送神难下一句是什么目录请神容易送神难下一句是什么请神容易送神难,难缠贵,十二生肖里指的是那个...
汽车保养一次大概需要多少钱（4... 今天给各位分享汽车保养一次大概需要多少钱的知识，其中也会对4s店保养一次多少钱进行解释，如果能碰巧解...
linux——文本及字符的检索... 文件夹中的目标文件名搜索 find 查询某个文件夹中的某文件：find directo...
手把手教你使用QT语言专家实现... qt版本：5.14.1qtCreator版本：4.11.1硬件ÿ...
线程安全问题，两种锁（sync... 安全问题 多个线程同时操作一个共享数据时，就有可能造成错误，如重复操作&...
神经网络算法 SamNum = 100; % 总样本数 TestSamNum = 101; % 测...
奔腾B70怎么样-车主点评-真... 今天给各位分享奔腾B70怎么样-车主点评-真实评价-口碑的知识，其中也会对奔腾b70这车质量到底怎么...
乐驰1.0油耗真实油耗多少（乐... 本篇文章极速百科给大家谈谈乐驰1.0油耗真实油耗多少，以及乐驰10几个油对应的知识点，希望对各位有所...
女人梦见老虎是什么预兆,女人梦... 女人梦见老虎是什么预兆目录女人梦见老虎是什么预兆女人梦到老虎预示着什么意思梦见老虎是什么意思女人梦见...
出门旅游必带的物品有哪些,旅游... 出门旅游必带的物品有哪些目录出门旅游必带的物品有哪些旅游带些什么必备用品出行旅游应该带些什么？出门旅...
数据分析Numpy之布尔索引 布尔数据：只有两种值，即真（True）或假&...
深入理解JVM虚拟机（二） 目录： （1）堆 （2）堆-内...
【Java SE】变量的本质 目录一. 前言二. 变量(variable)2.1 性质2.2 变量类型2.2.1 核心区别2.3 ...