Re: [閒聊] 每日LeetCode

: ※ 引述《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 : } 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