[問題] 一維陣列中最長位置連續但數值相異整數

[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

--
World of bleed1979

http://bleed1979.myweb.hinet.net/


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.133.60
→ maplefog:請問什麼是最長連續相異整數，又連續又相異?
推 Ebergies:連續是指位置連續, 相異是指數字相異
推 jlovet:後項減前項,差不等於1的就記下來
→ jlovet:找最長得不等於一的
→ bleed1979:我修改一下標題和原文　以免看的人誤會了
※ 編輯: bleed1979       來自: 118.168.133.60       (04/29 11:34)
推 Ebergies:三樓這樣會找到 1 2 4 3 1 5
→ Ebergies:看來只是誤會題目 XDD
→ jlovet:喔喔,我知道你的意思了
推 Ebergies:我的建議是弄個 hash 再用你 "很快" 的方法解
→ adrianshum:贊同樓上... 不用 STL, 也能做 hashtable/map 之類呀
推 ledia:假設答案是 k, 你可以 O(n) 驗證有沒有長度 k 的答案
→ ledia:binary search k, 整個問題的複雜度就是 O(kn), 不用 hash
→ ledia:更正.... 驗證還是要用 hash
→ ledia:不然會變成 O(klgk * n)
推 ledia:不用 hash 的驗證方式是用一個 heap 變形, 每次 len-k 的
→ ledia:咦 我想錯了 囧 再想想...
→ ledia:是 bst node 記次數才對....
推 chrisdar:兩個指標 O(N*N) 驗證指標內有沒有重複O(N) 總共O(N^3)
→ bleed1979:感謝大家　我現在正朝著hash table的方向努力
→ bleed1979:有結果再上來po文
推 gba356:限四這個數據（一百萬）應該是要求 O(NlgN) 以下的意思吧？