一个帖子http://www.iteye.com/topic/790362的一个题目。
有两个长度分别为m,n的非递减 整型数组,其中n>m*m, 求这两个数组的交集,要求复杂度尽可能低 。
如数组a:-1,4,5
数组b:-15,1,3,4,5,7,8,9,10,15
结果应该是:4,5
这道题要充分利用n > m * m的条件,而无论是归并的方式,还是hashset的方式复杂度都和两个数组的长度大小比例无关,复杂度都是n+m > m * m + m = m(m+1) = O(m^2)。
使用二分查找,从小的集合中的元素依次二分查找大集合,得到公共元素的复杂度为:
m * logn = m* log(m^2) = 2m * logm = O(m*logm),我感觉这也是题目的原意。
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class CommonElements {
public static Set<Integer> commonElements(int[] a,int[] b){
Set<Integer> commonElements = new HashSet<Integer>();//use set to avoid duplication
int[] temp;
if(a.length > b.length){//swap if a.length > b.length
temp = a;
a = b;
b = temp;
}
for(int e : a){//for each element in a binary search from b
int index,preIndex = 0;
index = Arrays.binarySearch(b,preIndex,b.length, e);
if(index >= 0){
preIndex = index;
commonElements.add(e);
}
}
return commonElements;
}
public static void main(String[] args) {
int[] a = {-1,4,5};
int[] b = {-15,1,3,4,5,7,8,9,10,15};
Set<Integer> commonElements = CommonElements.commonElements(a,b);
for (Integer element : commonElements) {
System.out.println(element);
}
}
}
分享到:
相关推荐
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 ...
大连华信去年的笔试题,可以给各位即将工作的同学一些参考
嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集...
用友笔试题用友笔试题用友笔试题用友笔试题用友笔试题用友笔试题用友笔试题
c笔试题c笔试题c笔试题c笔试题c笔试题c笔试题
C#笔试题大全C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.,让你...
2016 年 杭电 笔试 第二题 Ruby解法
c++笔试题汇总c++笔试题汇总c++笔试题汇总c++笔试题汇总c++笔试题汇总c++笔试题汇总c++笔试题汇总c++笔试题汇总
java 笔试题 j2ee笔试题 java笔试题 j2ee 笔试题
JAVA笔试题,面试题JAVA笔试题,面试题JAVA笔试题,面试题JAVA笔试题,面试题JAVA笔试题,面试题
中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 v中兴笔试题 中兴笔试题 ...中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题
赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融...
C++ 笔试题汇总 C++ 笔试题汇总 C++ 笔试题汇总 C++ 笔试题汇总
软件公司笔试题软件公司笔试题软件公司笔试题
百度笔试题 百度 笔试题 百度 笔试题
c++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rar
笔试题 c语言 智力题 笔试题 c语言 智力题 笔试题 c语言 智力题