import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CommonItemInTwoSortedArray {
/**
* 题目:给定两个已排序序列,找出共同的元素。
* 1.定义两个指针分别指向序列的开始。
* 如果指向的两个元素相等,则找到一个相同的元素;如果不等,则将指向较小元素的指针向前移动。
* 重复执行上面的步骤,直到有一个指针指向序列尾端。
* 2.如果数组大小差得很多,就遍历小的,然后在大的里二分查找
*/
public static void main(String[] args) {
int[] a={1,3,5,7};
int[] b={2,3,4,5,6,8};
List<Integer> c=findCommonItems(a,b);
for(int each:c){
System.out.print(each+" ");
}
}
public static List<Integer> findCommonItems(int[] a,int[] b){
List<Integer> commonList=new ArrayList<Integer>();
if(!(a!=null&&a.length>0&&b!=null&&b.length>0)){
return commonList;
}
int lenA=a.length;
int lenB=b.length;
/*
if(lenA<lenB){//how do we know lenB is much bigger than lenA? lenB>=100*lenA? or lenB>=1000*lenA?...
for(int each:a){
int index=Arrays.binarySearch(b,each);//we can write our own binarySearch for practice.
if(index>=0){
commonList.add(each);
}
}
return commonList;
}
*/
for(int i=0,j=0;i<lenA&&j<lenB;){
if(a[i]<b[j]){
i++;
}else if(a[i]==b[j]){
commonList.add(a[i]);
i++;
j++;
}else if(a[i]>b[j]){
j++;
}
}
return commonList;
}
}
分享到:
相关推荐
最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和Y的一个最长公共子序列。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据...
用java语言编写的产生一个N位随机序列的代码
Java-Thread-Affinity,将Java线程绑定到给定的内核.zip
给定两个整型数组,本题要求找出不是两者共有的元素。 输入格式: 输入分别在两行中给出两个整型数组,每行先给出正整数N(≤20),随后是N个整数,其间以空格分隔。 输出格式: 在一行中按照数字给出的...
java实现--输出给定范围内的质数。。。。。。。。。。。
给定长度为n的一个序列,分别进行插入排序、归并排序以及快速排序,并输出其运行时间。 数据输入 随机生成规模为n的数据,写入输入文件input.txt 结果输出 1.读入input.txt,分别运行上述三种排序,并将结果输出到...
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=, x2,…, xm>,则另一序列Z=, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 , i2,…, ik>,使得对于所有j=1,2,…,k有:...
13,15,17,19),其中位数是15,若b=(2,4,6,8,20),其中位数为6。两个等 长有序序列的中位数是含它们所有元素的有序序列的中位数,例如a、b两 个有序序列的中位数为11。设计一个算法求给定的两个有序序列的中 位数。
字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉...给定两个字符序列A和B,如果字符序列Z既是A的子序列,又是B的子序列,则称序列Z是A和B的公共子序列。该问题是求两序列A和B的最长公共子序列(LCS)。
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=, x2,…, xm>,则另一序列Z=, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 , i2,…, ik>,使得对于所有j=1,2,…,k有
输入两个非降序列,转换成两个非升序列,合并成一个非升序列。
给定⼀一个有序递增的整数序列列,判断它是否为⼀一个阶梯序列列 阶梯序列列的定义为:假如存在⼀一个数,这个数右边的⼦子序列列之和是左边的⼦子序 列列之和的两倍,即为阶梯序列列 样例例: 输⼊入:第⼀一⾏行行...
给定n 个整数组成的序列,现在要求将序列分割为m 段,每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小? 编程任务: 给定n 个整数组成的序列,编程计算该序列的最优m 段分割,...
简单插入排序思想,将一个无序的数组,想象成由两部分组成,一部分为有序列,一部分为无序列,初始时,有序列为数组第一个元素,无序列为第一个元素之后的元素组成。每次从无序列中取第一个数插入到有序列中,有序列...
cpp代码-给定两个数,求这两个数的最大公约数
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。示例 1:输出:4解释:最长数字连续序列是 [1, 2, 3
用JAVA做两个给定时间的天数差
给定10个整数的序列,要求对其重新排序。排序要求: 1.奇数在前,偶数在后; 2.奇数按从大到小排序; 3.偶数按从小到大排序。 【输入】 输入一行,包含10个整数,彼此以一个空格分开,每个整数的范围是大于等于0,...
求一个序列的全排列,字典序,序列中的元素无重复,在实际应用过程中,可以按下标来做计算
java代码-使用java解决给定一个整数N,编写程序求1!+2!+……+N!的源代码 ——学习参考资料:仅用于个人学习使用!