一个帖子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++技能测试试卷二及答案....
中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 v中兴笔试题 中兴笔试题 ...中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题
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#笔试题大全.,让你...
2013年四川移动校招笔试题.zip 2014年中国移动招聘笔试试题及答案.pdf 2015年中国移动招聘笔试试题及答案.pdf 移动笔试真题之市场营销类--中国移动校园招聘客服人员试题及答案.pdf 移动笔试真题之技术类--2010年厦门...
【大疆创新嵌入式笔试题】涉及到的IT知识点涵盖了编程基础、嵌入式系统、处理器中断处理、通信协议以及系统设计等多个方面。以下是对这些知识点的详细解释: 1. **编程基础** - **结构体内存占用**:在64位机器上...
c++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rar
JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题...
有一组字符串,需要对它进行远程读取并按照规则进行逐行排序。 排序规则: 1. 字符规则(注意:区分大小写):j 2. 最后一列(1,2,3,4,5)需出现在排序后的第一列 3. 排序后输出的内容格式保持不变(即两两一组,...
阿里巴巴校招前端笔试题 校招前端笔试题.pages
创新工场校招研发笔试题.pdf 小米校招技术类笔试题.pdf 届阿里巴巴校招测试开发工程师在线笔试题.pdf 年欢聚时代校园招聘C++笔试题目.pdf 年欢聚时代(YY)校园招聘Java笔试题目.pdf 网易校招JAVA开发工程师.pdf ...
该文件为山大地纬Java开发岗笔试试题 该文件为山大地纬Java开发岗笔试试题 该文件为山大地纬Java开发岗笔试试题 该文件为山大地纬Java开发岗笔试试题 该文件为山大地纬Java开发岗笔试试题
这份笔试题集不仅揭示了游戏开发的基本技能要求,也反映了行业对创新思维和问题解决能力的重视。下面我们将深入探讨其中涉及的关键知识点,并提供应对这类笔试题的策略。 一、编程基础 在游戏开发中,扎实的编程...
《2021紫光笔试题IC校招笔试题》是一个针对集成电路(IC)行业的笔试题目集合,主要针对应届毕业生的招聘过程。紫光集团是中国知名的集成电路设计与制造企业,其笔试题目的涵盖范围广泛,旨在测试应聘者的专业知识、...
数字马力笔试题 本文总结了数字马力的笔试题,涵盖了软件测试岗位的简历筛选笔试题,涉及到了接口自动化测试、Java/Python 实现多线程的方法等知识点。 接口自动化测试 在软件测试中,接口自动化测试是一个重要的...
荣耀笔试题总结.docx
2009福富笔试题(java,c/c++)海外,电信 以下是从给定的文件信息中生成的相关知识点: 1. 复习要点1.jsp 基础(转向,9 大对象) 知识点:jsp 基础、服务器端编程、Java Web 开发 解释:jsp 是一种服务器端编程语言...