→ bleed1979:已回信... 04/30 00:52
※ 引述《bleed1979 (十三)》之銘言：
: 想請教在不用STL的情況下, 也就是以C語言來解有沒有更好的演算法
: 一維陣列：1, 2, 4, 3, 1, 5
: 最長位置連續但數值相異整數序列為 2, 4, 3, 1, 5
: 思考上有幾個限制
: 限制1.不能使用STL(用Map解就很快了)
: 限制2.整數最小為1, 最大到10^9(動態宣告即使是char也會超出規定的記憶體限制)
: 限制3.一定是位置連續相異(不太能排序解, 排序解適用位置不連續的情況)
: 限制4.陣列長度為100萬個
: 我的演算法為
: 分成左指標和右指標
: 左指標代表序列開頭, 右指標依序向右遞增
: 如果右指標指到的數可以在兩個指標之間(含左指標, 不含右指標)找到的話
: 設一個變數代表最長相異序列的長度, 小於右指標 - 左指標 + 1 就更新其值
: 左指標更新為指向找到位置 + 1
: 這個演算法耗費大量時間在找兩個指標之間的數
: 因為連續相異我只得用循序的方式查找
: 最差情況是O(n^2)
: 請教更高效率的演算法
: Bleed
sorry~ 我有點搞混了
它的意思是 在他給的 1D array中
從[1]開始 連續取值 到一個set中 直到不能insert到set中為止 的長度
稱作 從[1]開始的(相異)雪花數量 對吧?
so 從開頭[1]~[10^6] 每一個都算出雪花數量後
找出最大的雪花數量 稱作 最大(相異)雪花數量 對嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.122.53