只是要把功能做出來不難，難在要怎樣提高效率

目前在這題我嘗試過的幾種思路

• 極度懶人解:
  • 導入 statistics 的 median，用前輩們寫好的工具求中位數
  • 好處是只要兩三行就能搞定
  • 壞處是會吃 TLE (笑
    
    
• 自己實現 statistics.median 的算法，並針對題目優化
  • 查看源代碼(Python 3.12)，可以找到像這樣的內容 
    
  • 可以看到每次執行都會先檢查傳入的資料裡面有沒有東西，然後才可能回傳中位數，但我們不需要這麼做，因為在這題目，我們可以確定這種事不會發生，那就不需要再多 if 一次了，直接跳過
  • 如果你是用 list 保存所有數字的話，用 list.sort() 的效率會比 sorted() 略高一點點，statistics.median 主要是考慮可能有人會傳其他類型的數據進去才用 sorted()
  • 寫法大同小異，主要就少一個 if 而已
  • 放心，有好好修改過的話，不會吃 TLE，寫起來也簡單
    
    
• 插入排序法 Insert Sort
  • 數字是一個一個拿的，為什麼我們需要每次拿到新數字就要跑一次完整的 sort 呢?
    每執行一次 sort()，程式就需要檢查所有數字並排序，太囉嗦了，何不拿到數字後就直接找一個合適的風水寶地，直接把新的數字插入對應的位置? 這個思路就是插入排序法。
  • 但要怎要找該在哪裡插入數字? 我嘗試了兩個做法: 線性搜索和二分搜
    • 線性搜索:
      • 很簡單，每次得到新的數字，就從 list 的第 0 個位置由左至右一一比較，當發現數字大於等於新數字時，那就是要插入數字的位置。
        

        # 線性搜找插入的位置 for idx in range(len(number_list)): if number_list[idx] >= num: numbers.insert(idx, num) break else: number_list.append(num)

      • 然後你就會吃 TLE，測資挺大的，用線性搜的話會很花時間，時間複雜度是 O(n)
        
        
    • 二分搜:
      • 二分搜的時間複雜度是 O(log n)，效率會比線性搜好很多很多，對 python 來說有兩種做法
      • 一個是自己實現，需要維護兩個指針尋找目標位置
        

        # 二分搜找插入的位置 lft, rgt = 0, length while lft < rgt: mid = (lft + rgt) // 2 if numbers[mid] < num: lft = mid + 1 else: rgt = mid numbers.insert(lft, num)

      • 另一個作法就比較懶，但效率反而更高，導入 bisect 的 bisect_left 就可以了，它在做的事情和上面那串程式碼幾乎一樣，差別在於 bisect 是用 C 寫的，所以效率比較好，bisect 就是專門用來處理數字該在哪插入的
        
        
• 對頂堆積
  • 動態計算一系列數字中第 n 個數字 (or 中位數) 時，就是對頂堆積的主場
  • 需要維護兩個堆，分別是最大堆 Max Heap 和最小堆 Min Heap ，並在過程中確保這兩個堆的元素總數是平均分配的，求平均數時，就只需要直接從最大堆和最小堆的最上面直接拿答案出來就可以了
  • python 可以導入 heapq 做這件事
  • 我的作法: gist