Re: [閒聊] 每日LeetCode
看板Marginalman作者sustainer123 (caster )時間2年前 (2023/11/17 12:00)推噓0(0推 0噓 0→)留言0則, 0人參與討論串524/719 (看更多)
: : 今天要問你
: : 一串陣列裡面數字 兩個一組加起來平均最小
: : 會出現的最大數字
: : 舉例 [1,2,3,4,5,6] 會變成 [1+6,2+5,3+4]
: : 也就是[7,7,7] 所以最大的數字是7
: Intuition:
: 排序之後大小配。
: Approach:
: 求最小的最大值
: 一定是陣列中最大元素與最小元素配
: 次大元素與次小元素配
: 所以排序之後頭尾配對就能找到最佳解
: 後來看別人的解法
: 發現這一題的數字範圍只有到10^5
: 所以可以直接宣告一個10^5大小的陣列
: 然後跑一次迴圈把數字塞進去
: 就可以不用排序
: 把時間複雜度減到O(n)
: TS Code:
: function minPairSum (nums: number[]): number {
: nums.sort((a, b) => (a - b))
: let answer = 0
: for (let index = 0; index < nums.length / 2; index++) {
: answer = Math.max(answer, nums[index] + nums[nums.length - index - 1])
: }
: return answer
: }
Python Code:
class Solution:
def minPairSum(self, nums: List[int]) -> int:
nums.sort()
l = []
for i in range(len(nums)//2):
l.append(nums[i]+nums[-(i+1)])
return max(l)
暴力解
排序後找最大值就能得到答案
補字補字補
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.119.121.6 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700193618.A.1D0.html
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 524 之 719 篇)：