百度软件开发面试题:现有数据A[]和数组B[],数组A和B的元素个数可能相差很多,但也可能几乎相同。要求有什么方法能尽快找出数组A和B的交集元素。说明时间和空间复杂性是多少
- 方案一:使用两个for循环遍历两个数组,时间复杂度为O( n2),空间复杂度O(1)
- 方案二:将两个数组排好序,之后设置两个数组的下标i=0,j = 0,从头到尾扫描两个数组中数是否相同,如果不同,较小的数靠后移位,如果相同,则两个下标同时后移,直到其中一个下标到了末尾,则结束。时间复杂度为O( nlogn),空间复杂度O(1)
- 方案三:对长度较短的数组建立hash表,然后利用较长的数组在hash表中查找是否存在。时间复杂度为O(1),空间复杂度O(min(N,M))
声明:本站部分文章及图片源自用户投稿,如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢!