作者bleed1979 (十三)
看板C_and_CPP
標題[問題] 一維陣列中最長位置連續但數值相異整數
時間Wed Apr 29 10:45:34 2009
想請教在不用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
--
World of bleed1979
http://bleed1979.myweb.hinet.net/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.133.60
1F：→ maplefog:請問什麼是最長連續相異整數，又連續又相異? 04/29 10:55
2F：推 Ebergies:連續是指位置連續, 相異是指數字相異 04/29 10:57
3F：推 jlovet:後項減前項,差不等於1的就記下來 04/29 11:27
4F：→ jlovet:找最長得不等於一的 04/29 11:27
5F：→ bleed1979:我修改一下標題和原文 以免看的人誤會了 04/29 11:31
※ 編輯: bleed1979 來自: 118.168.133.60 (04/29 11:34)
6F：推 Ebergies:三樓這樣會找到 1 2 4 3 1 5 04/29 11:34
7F：→ Ebergies:看來只是誤會題目 XDD 04/29 11:35
8F：→ jlovet:喔喔,我知道你的意思了 04/29 11:46
9F：推 Ebergies:我的建議是弄個 hash 再用你 "很快" 的方法解 04/29 11:48
10F：→ adrianshum:贊同樓上... 不用 STL, 也能做 hashtable/map 之類呀 04/29 11:54
11F：推 ledia:假設答案是 k, 你可以 O(n) 驗證有沒有長度 k 的答案 04/29 12:03
12F：→ ledia:binary search k, 整個問題的複雜度就是 O(kn), 不用 hash 04/29 12:03
13F：→ ledia:更正.... 驗證還是要用 hash 04/29 12:04
14F：→ ledia:不然會變成 O(klgk * n) 04/29 12:04
15F：推 ledia:不用 hash 的驗證方式是用一個 heap 變形, 每次 len-k 的 04/29 12:06
16F：→ ledia:咦 我想錯了 囧 再想想... 04/29 12:07
17F：→ ledia:是 bst node 記次數才對.... 04/29 12:07
18F：推 chrisdar:兩個指標 O(N*N) 驗證指標內有沒有重複O(N) 總共O(N^3) 04/29 12:11
19F：→ bleed1979:感謝大家 我現在正朝著hash table的方向努力 04/29 14:52
20F：→ bleed1979:有結果再上來po文 04/29 14:52
21F：推 gba356:限四這個數據（一百萬）應該是要求 O(NlgN) 以下的意思吧？ 04/29 16:36