LeetCode 1877. 数组中最大数对和的最小值

简介: 一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。

网络异常,图片无法展示
|


题目


一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。


比方说,如果我们有数对 (1,5) ,(2,3) 和 (4,4),最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。 给你一个长度为 偶数 n 的数组 nums ,请你将 nums 中的元素分成 n / 2 个数对,使得:


nums 中每个元素 恰好 在 一个 数对中,且 最大数对和 的值 最小 。 请你在最优数对划分的方案下,返回最小的 最大数对和 。

 

示例 1:
输入:nums = [3,5,2,3]
输出:7
解释:数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。
示例 2:
输入:nums = [3,5,4,2,4,6]
输出:8
解释:数组中的元素可以分为数对 (3,5),(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。


提示:


n == nums.length 2 <= n <= 105 n 是 偶数 。 1 <= nums[i] <= 105


解题思路


class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        # 先排序,然后头尾遍历,找出最低值
        nums.sort()
        res = 0
        for i in range(len(nums)//2):
            dui = nums[i] + nums[len(nums) - 1 - i]
            if dui>res:
                res = dui
        return res
if __name__ == '__main__':
    nums = [3,5,4,2,4,6]
    ret = Solution().minPairSum(nums)
    print(ret)
目录
打赏
0
0
0
0
1
分享
相关文章
|
5月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
63 0
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
161 2
|
7月前
|
【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
解决剑指Offer题目 "数组中重复的数字" 的Python实现方法,通过使用字典来记录数组中每个数字的出现次数,快速找出重复的数字。
59 1
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
LeetCode------移动零(5)【数组】
这篇文章介绍了LeetCode上的"移动零"问题,提出了一种使用双指针的原地操作解法,该方法首先将非零元素移动到数组前端并保持相对顺序,然后填充后续位置为零,以达到题目要求。
|
5月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
39 4
|
5月前
|
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
42 0
Leetcode第三十三题(搜索旋转排序数组)
|
5月前
|
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
95 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等