问题:有两个有序整数集合a和b,写一个函数找出它们的交集?
题目的意思应该是这样的,直接写不算难,我觉得应该是考写出比较高效的算法
大家帮忙回答。
我对上边的代码优化了一下,做了两个对比,贴出来大家看看:
import java.util.ArrayList;
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Test test = new Test();
test.test1();
test.test2();
}
public void test1() {
int[] a = { 2, 3, 4, 4, 4, 4, 7, 8, 8, 8, 8, 9, 100, 130, 150, 160 };
int[] b = { 4, 6, 7, 7, 7, 7, 8, 8, 9, 10, 100, 130, 130, 140, 150 };
int i = 0, j = 0, k = 0, m = 0, n = 0;
ArrayList al = new ArrayList();
while (i < a.length && (j < b.length)) {
if (a[i] < b[j]) {
i++;
m++;
}
else if (a[i] > b[j]) {
j++;
n++;
}
else {
al.add(a[i]);
i++;
j++;
}
k++;
k++;
}
System.out.println("交集:"+al);
System.out.println("循环体比较次数:"+k);
System.out.println("m比较次数:"+m);
System.out.println("n比较次数:"+n);
System.out.println("总比较次数:"+(int)(k+m+n));
}
public void test2() {
int[] a = { 2, 3, 4, 4, 4, 4, 7, 8, 8, 8, 8, 9, 100, 130, 150, 160 };
int[] b = { 4, 6, 7, 7, 7, 7, 8, 8, 9, 10, 100, 130, 130, 140, 150 };
int i = 0, j = 0, k = 0, m=0,n=0,x = 0, y = 0;
ArrayList al = new ArrayList();
while (i < a.length && (j < b.length)) {
while(i < a.length-1&&a[i]==a[i+1]) {
i++;
x++;
x++;
}
while(j < b.length-1&&b[j]==b[j+1]) {
j++;
y++;
y++;
}
if (a[i] < b[j]) {
i++;
m++;
}
else if (a[i] > b[j]) {
j++;
n++;
}
else {
al.add(a[i]);
i++;
j++;
}
k++;
k++;
}
System.out.println("交集:"+al);
System.out.println("循环体比较次数:"+k);
System.out.println("x排除重复比较次数:"+x);
System.out.println("y排除重复比较次数:"+y);
System.out.println("m比较次数:"+m);
System.out.println("n比较次数:"+n);
System.out.println("总比较次数:"+(int)(k+m+n+x+y));
}
}
运行结果:
交集:[4, 7, 8, 8, 9, 100, 130, 150]
循环体比较次数:44
m比较次数:7
n比较次数:7
总比较次数:58
交集:[4, 7, 8, 9, 100, 130, 150]
循环体比较次数:24
x排除重复比较次数:12
y排除重复比较次数:10
m比较次数:2
n比较次数:3
总比较次数:51
可以看到优化的代码效率略微有所改进,结果也更合理。
分享到:
相关推荐
整理了一下阿里巴巴往届笔试面试题,希望对大家有帮助: 来源:阿里巴巴笔试面试圈>> 1、史上最全Java面试266题:算法+缓存+TCP+JVM+搜索+分布式+数据库 2、2018阿里软件工程师笔试题 3、2018秋招阿里巴巴java...
阿里巴巴校招前端笔试题 校招前端笔试题.pages
刚刚参加的阿里巴巴的笔试题。看看你与大公司的差距。 绝对有收藏价值!
阿里巴巴2014笔试题(客户端)
2014年3月阿里巴巴实习招聘笔试题及部分答案.docx 2014年阿里巴巴校园招聘笔试题杭州站-研发类.doc 淘宝2011实习招聘笔试.doc 淘宝校园招聘清华笔试试题.doc 淘宝校园招聘笔试试题.doc 淘宝笔试题及部分答案.docx ...
阿里巴巴多岗位校园招聘笔试真题汇总-2021 包含多个岗位方向的校园招聘笔试真题: 交互设计师岗 产品运营岗 技术web前端开发岗 技术岗位通识 游戏运营岗 用户体验实习生岗 研发工程师岗 营销专员岗 视觉设计师岗 ...
本资源为阿里巴巴DBA笔试题,包括答案,涵盖了DBA和ETL工程师需要掌握的知识点。下面将逐一解读题目中的知识点。 一、SQL Tuning 1. 表连接方式:Hash Join、Merge Join、Nest Loop(Cluster Join)、Index Join等...
《技术之瞳——阿里巴巴技术笔试心得》由阿里巴巴集团校园招聘笔试项目组所著,收集了阿里历年校招中的精华笔试题,涉 及多个领域。《技术之瞳——阿里巴巴技术笔试心得》中内容大量结合了阿里巴巴的实际工作场景,...
【阿里巴巴2014笔试题及答案】涉及的IT知识点主要集中在编程语言C++、算法与数据结构、Unity 3D手机游戏开发以及计算机基础知识上。以下是对这些知识点的详细说明: 1. **C++**: 笔试题中涉及到C++的基础语法和编程...
文档是2014年阿里巴巴实习生笔试题。各个岗位的基础题是一样的,只是附加题不一样
根据给定的文件信息,以下是对“阿里巴巴公司DBA笔试题”中提到的关键知识点的详细解释: ### 一、SQL性能调优 #### 1. 不同类型的JOIN操作 - **Hash Join**: 当两个表中都有大量数据时,通常会选择哈希连接。它...
阿里巴巴2011年笔试试题集合阿里巴巴2011年笔试试题集合阿里巴巴2011年笔试试题集合阿里巴巴2011年笔试试题集合阿里巴巴2011年笔试试题集合阿里巴巴2011年笔试试题集合
07-08年阿里巴巴的笔试题
根据提供的信息来看,本次分享的主题是“阿里巴巴客户端笔试题”,但是由于题目图片未给出具体内容,因此,本篇文章将基于常见的阿里巴巴技术笔试题型,总结出可能涉及的技术知识点,并对这些知识点进行详细的阐述。...
阿里巴巴 技术类 笔试题 有实习生笔试题 图片
阿里巴巴java面试题目,涵盖全部的Java高级技术,数据库技术和分布式相关技术。
阿里巴巴作为中国知名的互联网巨头,其校园招聘笔试题往往包含了丰富的IT知识,旨在考察应聘者的综合素质和技术实力。这套笔试题在南京大学进行,涵盖了多个技术领域,对于准备进入IT行业的学生或者想要提升自己的...
阿里巴巴B2B笔试题是求职者进入阿里巴巴B2B部门时可能会遇到的一系列技术与非技术测试题目。这些试题旨在评估应聘者的综合素质、技术能力、解决问题的技巧以及对互联网行业的理解。以下是对这些笔试题目的可能涵盖的...