推 oin1104: 我也是直接賽進100001裡面 好爽 11/17 11:49
推 sustainer123: 大師 11/17 11:58
※ 引述《oin1104 (是oin的說)》之銘言：
: https://i.imgur.com/WSG6EUy.png
: 今天要問你
: 一串陣列裡面數字 兩個一組加起來平均最小
: 會出現的最大數字
: 舉例 [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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700192901.A.13B.html