作者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/cn.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