[問題] 一維陣列中最長位置連續但數值相異的序列
想請教在不用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
→
04/29 10:55, , 1F
04/29 10:55, 1F
推
04/29 10:57, , 2F
04/29 10:57, 2F
推
04/29 11:27, , 3F
04/29 11:27, 3F
→
04/29 11:27, , 4F
04/29 11:27, 4F
→
04/29 11:31, , 5F
04/29 11:31, 5F
※ 編輯: bleed1979 來自: 118.168.133.60 (04/29 11:34)
推
04/29 11:34, , 6F
04/29 11:34, 6F
→
04/29 11:35, , 7F
04/29 11:35, 7F
→
04/29 11:46, , 8F
04/29 11:46, 8F
推
04/29 11:48, , 9F
04/29 11:48, 9F
→
04/29 11:54, , 10F
04/29 11:54, 10F
推
04/29 12:03, , 11F
04/29 12:03, 11F
→
04/29 12:03, , 12F
04/29 12:03, 12F
→
04/29 12:04, , 13F
04/29 12:04, 13F
→
04/29 12:04, , 14F
04/29 12:04, 14F
推
04/29 12:06, , 15F
04/29 12:06, 15F
→
04/29 12:07, , 16F
04/29 12:07, 16F
→
04/29 12:07, , 17F
04/29 12:07, 17F
推
04/29 12:11, , 18F
04/29 12:11, 18F
→
04/29 14:52, , 19F
04/29 14:52, 19F
→
04/29 14:52, , 20F
04/29 14:52, 20F
推
04/29 16:36, , 21F
04/29 16:36, 21F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 5 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
13
17
