Re: [問題] 一維陣列中最長位置連續但數值相異的序列
我又來了, 這表示有結果了
這題其實是ACM UVa的題目, 不用會員即可觀看的網址如下：
http://zerojudge.tw/ShowProblem?problemid=d194
不論題目的描述, 就是求位置連續但數值相異的最長序列
如果以上一篇文提到的演算法在 Zero Judge 是可以 AC 的, 因為測資不到100萬個
但在 ACM UVa 那裡就行不通了,而且限定的秒數比一般3.000秒還短的是2.000秒
所以怎麼傳怎麼TLE
先把演算法化為程式, 跑一次的程式碼如下：
==================================================
scanf("%d", &snowflakes[0]);
for(i = 0, j = 1, max = 0; j < n; ++j)
{
scanf("%d", &snowflakes[j]);
for(x = j - 1; x >= i; --x)
{
if(snowflakes[j] == snowflakes[x])
{
if(max < j - i)
{
max = j - i;
}
i = x + 1;
break;
}
}
}
if(max < j - i)
{
max = j - i;
}
printf("%d\n", max);
==============================================
i 表示左指標, j 表示右指標
內for迴圈就是循序查找的過程
最差的情況(全部相異) 1 + 2 + 3 + 4 + ... + n 次 = (n * (n + 1)) / 2
大概是O(n^2)的等級
而我說過如果用 C++ 的 STL 的 map 會有比較快的解答
演算法其實是一樣的, 程式碼如下：(snowflake 在此是 map<int, int> )
======================================================
max = left = 0;
snowflakes.clear();
for (i = 1; i <= n; ++i)
{
scanf ("%d", &flake);
if(left < snowflakes[flake])
{
left = snowflakes[flake];
}
snowflakes[flake] = i;
if(max < i - left)
{
max = i - left;
}
}
printf("%d\n", max);
======================================================
C++ 的寫法其速度大概是 C (上面那個程式) 的1/6倍 - 196ms 對 1.2s
而今天聽從網友的建議, 我去找了 C 的 Hash Table 的程式碼
經過修改後竟也過了, 其速度提升到 C++ 的1.5倍 - 276ms
可惜我改的這個程式是有版權的, 為表尊重不好公開, 但我提供網址如下：
Google 搜尋 "c hash table"
http://www.cl.cam.ac.uk/~cwc22/hashtable/
這個網站主人實作了 C 的 hash table 程式
我的作法是將 標頭檔 和 .c檔 全部加在一起, 並修改 search 的函式
search 函式在找到相同的 key 值會以新的 data 值替代舊的
所以傳入一個指標去存舊的 data 值, 才能實行 left 和 舊data值 比對的 if 敘述
另外要自行找 hash function
Google 搜尋 "hash function integer"
http://www.concentric.net/~Ttwang/tech/inthash.htm
我用的是 Robert Jenkins' 32 bit integer hash function 這個
附帶一提的是, 網站主人所寫的 destroy hash table 程式似乎有問題
上傳都是 runtime error, 最後我索性用註解槓掉, 不 free 記憶體的結果才過的
不過這樣不太好, 但至少運算過程其答案是對的
最後感謝大家提供的寶貴意見, 忙了一天總算有點收穫
接下來是好好研究這些程式的寫法
Bleed
--
World of bleed1979
http://bleed1979.myweb.hinet.net/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.133.60
推
04/29 22:04, , 1F
04/29 22:04, 1F
→
04/29 22:04, , 2F
04/29 22:04, 2F
→
04/29 22:05, , 3F
04/29 22:05, 3F
→
04/29 22:05, , 4F
04/29 22:05, 4F
→
04/29 22:06, , 5F
04/29 22:06, 5F
→
04/29 22:07, , 6F
04/29 22:07, 6F
→
04/29 22:07, , 7F
04/29 22:07, 7F
→
04/29 22:08, , 8F
04/29 22:08, 8F
→
04/29 22:09, , 9F
04/29 22:09, 9F
推
04/29 22:12, , 10F
04/29 22:12, 10F
推
04/29 22:16, , 11F
04/29 22:16, 11F
→
04/29 22:17, , 12F
04/29 22:17, 12F
→
04/29 22:18, , 13F
04/29 22:18, 13F
→
04/29 23:12, , 14F
04/29 23:12, 14F
推
04/29 23:13, , 15F
04/29 23:13, 15F
→
04/30 00:30, , 16F
04/30 00:30, 16F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 5 篇)：