作者bleed1979 (十三)
看板java
標題Re: [問題] 關於比對兩數列
時間Tue Oct 28 23:09:35 2014
※ 引述《sunsam777 (行善為樂)》之銘言：
: 數列一 整數陣列 值 1 2 3 4 5
: 數列二 整數陣列 值 3 5
: 要印出 數列二沒有的 1 2 4
: 請問該如何做呢?
: 我能想到的大概就是用兩個for迴圈
: 大概這樣，倆倆互相比對，共比10次 但要怎樣才能印出1 2 4呢
: 想了很久想不出來，可否指點下? 感謝不盡
不曉得題目的數列內容就是如此，還是經過原po轉換。
假設數列1有m個，數列2有n個：
時間複雜度一定是O(n)或O(m)以上的，因為至少要loop其中一個數列。
現在關心的是迴圈內的search.
每每loop一次肯定是最慢的，
有排序用binary search，沒排序或怕重複可以建tree或丟到Map,
數字範圍小的，開1000萬以上的陣列也可。
端看數列的長度和組成。大概是這樣。
--
Sent from my Android
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.203.156
※ 文章網址: http://webptt.com/m.aspx?n=bbs/java/M.1414508978.A.425.html
1F：推 mars90226: 有排序的只要O(max(m,n)) 10/28 23:14
2F：→ mars90226: 不需要search，用兩個index從數列前端往後走 10/28 23:15
3F：→ mars90226: 相同值就不理，兩個都+1。不同值，小的index+1，塞進結 10/28 23:16
4F：→ mars90226: 果裡面，這樣就可以走遍兩個數列 10/28 23:16
5F：→ mars90226: 好像應該是O(m+n) 10/28 23:17
6F：→ bleed1979: 是的。但前提是兩個數列皆排序過。 10/28 23:26