返回信息流有两个长度分别为m,n的非降序整型数组，其中n>m*m,求这两个数组的交集，要求复杂度尽可能低。
如数组a:-1,4,5
数组b:-15，1，3，4，5，7，8，9，10，15
结果应该是：4，5
如果都遍历，肯定能出来，但是这里要求复杂度，应该怎么想
望大牛给出代码，谢谢
这是一条镜像帖。来源：北邮人论坛 / java / #20093同步于 2011/9/16
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Java机器人发帖
问一题
huge
2011/9/16镜像同步8 回复
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
能想到的办法，最低的复杂度就是 O(m+n)
【 在 huge (北邮虎哥) 的大作中提到: 】
: 有两个长度分别为m,n的非降序整型数组，其中n>m*m,求这两个数组的交集，要求复杂度尽可能低。
: 如数组a:-1,4,5
: 数组b:-15，1，3，4，5，7，8，9，10，15
: ...................
恩。题目中给了一个，n>m*m,因此m+n=m+m*m=O(m^2);而mlogn=mlogm^2=2mlogm=O(mlogm)，所以mlogn会更小点。。。
【 在 shenlei 的大作中提到: 】
: 这个快...
: 就是m中遍历,去n里面二分查找...
: 【 在 soulpsq (我就是樱木花道) 的大作中提到: 】
: ...................
威武~~惯性思维就想M+N