学步园

Given two array of integers write two functions that will return an Union and Intersection

Time efficient
Both time and space efficient implemented

ANS1:经典.

To find the union:
Build a Binary Search Tree (BST1) from A1.
Insert values from A2. Check for equals.
If value already exists in BST1, store it in a second BST(BST2).
All the values from BST2 are intersections.
All the values added to BST1 are union.

ANS2:

package com.zhuyu_deng.test;
 
import java.util.Arrays;

public class Test
{
	public static void main(String args[])
	{
		int a[] = {1, 2, 3, 5};
		int b[] = {2, 4, 6, 7, 8, 1};
		int c[] = intersectionArrays(a, b);
		System.out.println(b.length);
		System.out.println(c.length);
		for (int i = 0; i < c.length; ++i)
			System.out.print(c[i] + " ");
	}                    
	private static int[] intersectionArrays(int[] a, int[] b)
	{
		Arrays.sort(a);
		Arrays.sort(b);
		int c[] = new int[a.length < b.length ? a.length : b.length];
		int i = 0, j = 0;
		int k = 0;
		while (i < a.length && j < b.length)
		{
			if (a[i] < b[j])
				i++;
			else if (a[i] > b[j])
				j++;
			else
			{
				c[k++] = a[i++];
				j++;
			}
		}
		
		int[] rst = Arrays.copyOfRange(c, 0, k);
		return rst;
		
	}
	
	private static int[] unionArrays(int[] a, int[] b)
	{
		Arrays.sort(a);
		Arrays.sort(b);
		int[] ans = new int[a.length + b.length];
		
		int i = 0, j = 0;
		int k = 0;
		while (i < a.length && j < b.length)
		{
			if (a[i] < b[j])
				ans[k++] = a[i++];
			else if (a[i] > b[j])
				ans[k++] = b[j++];
			else
			{
				ans[k++] = a[i++];
				j++;
			}	
		}
		while (i < a.length)
			ans[k++] = a[i++];
		while (j < b.length)
			ans[k++] = b[j++];
		
		int[]	rst = Arrays.copyOfRange(ans, 0, k);
		return rst;
	}
}