当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-给定两个已排序序列,找出共同的元素。

发表于: 2012-04-06   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class CommonItemInTwoSortedArray { /** * 题目:给定两个已排序序列,找出共同的元素。 * 1.定义两个指针分别指向序列的开始。 * 如果指向的两个元素
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;
	}
}

java-给定两个已排序序列,找出共同的元素。

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
已知一个从小到大已排序的元素序列,如何插入到stl set中最快。 1. stl set内部结构 我们知道stl se
有两个数组,需要找出这两个数组之间相同的元素。 package cn.luxh.jpa.test;import java.util.Hash
有两个数组,需要找出这两个数组之间相同的元素。 package cn.luxh.jpa.test;import java.util.Hash
题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的
本文为转载,原文地址是:http://blog.csdn.net/morewindows/article/details/8214003 题目:在一个
题目:输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对
DP方式求解: #include <iostream> using namespace std; /** * 问题描述:两个字符串,求解
计算序列中元素的位置 寻找序列中元素的位置,这里序列是有序的。根据序列中元素是否有重复分为无重
#include <iostream> using namespace std; int main() { int a[9],i; for(i=0;i<9;i++) c
1-N放在N+1个元素的数组中,只有唯一的一个元素值重复,其他均只出现一次。每个数组元素只能访问一
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号