#26786: O(n)的想法


406490150@gms.tku.edu.tw (我是朱朱)

學校 : 國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 :
2022-09-03 11:13:16
c669. missing and duplicate -- it's david | From: [218.173.238.128] | 發表日期 : 2021-08-24 22:43

假設x是數列,找出下面的東西很有用

  • 數列最大值

  • 數列最小值

  • 數列總和

  • 數列長度

  • 數列中重複的數字 (小提示: 可以用set,O(1)查找)

 

找出上述資料,再使用一些技巧得出下面的東西,就會越來越接近答案:

  • 等差級數公式:(上底+下底)*高/2  與  數列間的關係?

  • 數列總和 與 等差級數公式  的 差值 代表什麼呢?

 

如果你是先找「數列中缺少的數字」,似乎會比較困難哦?

是說,等差級數的公差需要知道嗎? :D

 
ZeroJudge Forum