很基础的求两个有序数组的交集和并集

 

 /**
     * 求解两个有序数组的交集
     * @param a
     * @param b
     * @return
     */
    public static List<Integer> join(int[] a , int[] b){
        List<Integer> list = new LinkedList<Integer>();
        int ai = 0;
        int bi = 0;
        while(ai < a.length && bi < b.length){
            if(a[ai] == b[bi]){
                //两个相等即交集
                list.add(a[ai]);
                ai++;
                bi++;
            }
            else if(a[ai] > b[bi]){
               //移动小得数组index
               bi++;
            }
            else{
                //移动小值得数组index
               ai ++;
            }
        }

        return list;
    }

    /**
     * 求解两个有序数组的并集
     * @param a
     * @param b
     * @return
     */
    public static List<Integer> merge(int[] a , int[] b){

        List<Integer> list = new LinkedList<Integer>();
        int ai = 0;
        int bi = 0;
        while(ai < a.length && bi < b.length){
            if(a[ai] < b[bi]){
                list.add(a[ai]);
                ai++;
            }
            else if(a[ai] > b[bi]){
                list.add(b[bi]);
                bi++;
            }
            else {
                list.add(a[ai]);
                ai++;bi++;
            }
        }

        //剩余的直接插入到结果集的末尾
        if(ai < a.length){
            for(;ai < a.length ; ai++){
               list.add(a[ai]);
            }
        }
        else if(bi < b.length){
            for(;bi < b.length ; bi++){
               list.add(b[bi]);
            }
        }

        return list;
    }

 

评论

3 楼 draem0507 2013-07-11  

for (int i = 0; i < a.length; i++) {
			for (int j = 0;j < b.length; j++) {
				if(a[i].compareTo(b[j])==0){
					list.add(a[i]);
					break;
				}else if(a[i].compareTo(b[j])>0){
					list.add(b[j]);
					
				}else {
					list.add(a[i]);
					break;
					
				}
			}
		}

2 楼 draem0507 2013-07-11  

public static List<Integer> join2(Integer[] a, Integer[] b) {
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < a.length; i++) {
			for (int j = 0;j < b.length; j++) {
				if(a[i].equals(b[j])){
					list.add(a[i]);
					break;
				}else if(a[i]<b[j]){
					break;
				}
				
			}
		}
		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
		
		return list;
	}

对时间复杂度还不是很懂 先mark下吧

1 楼 draem0507 2013-07-11  

List<Integer> alist = new ArrayList<Integer>();
		for (int i = 0; i < a.length; i++) {
			alist.add(a[i]);
		}
		List<Integer> blist = Arrays.asList(b);
		alist.retainAll(blist);

 blist.removeAll(alist);
    blist.addAll(alist);

算法不好的人,伤不起。。