有两个整型数组A和B，有什么高效的算法，找出两个数组的交集
A：3 1 20 46
B：20 9 12 5
交集：20
观点一：
数组A长度：m
数据B长度：n
----------------------------------------------
最直接两个数组挨个比: 时间 = m * n
----------------------------------------------
两个数组分别排序 时间 = m^2 + n^2 + m //m,n的平方 (最后得比一次吧)，这个好慢啊
---------------------------------------------
只排1个数组 时间 = n^2 + m //n的平方和m*n哪个大，好象省不了多少时间
观点二：
设这两个数组分别为A[N],B[M] (N <=M)
1)对A[N]排序 －－ 时间复杂度NlgN;
2)对B[M]中的每一个元素，在已经排序好的A[N]中二分查找 －－时间复杂度 MlgN
综上，时间复杂度为 (M+N)lgN
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。