In a file named MergeIntersect.java, implement a static method named intersect that takes two arrays of integers
Question:
In a file named MergeIntersect.java, implement a static method named intersect that takes two arrays of integers as parameters and uses an approach based on merging to find and return the intersection of the two arrays – i.e., all values that are found in both arrays.
More specifically, you should do the following:
Begin by creating a new array for the intersection. What should the length of this array be?
Use one of the more efficient sorting algorithms from Sort.java to sort both of the arrays.
Find the intersection of the two arrays by employing an approach that is similar to the one that we used to merge two sorted subarrays (i.e., the approach taken by the mergemethod in Sort.java). Your method should not actually merge the two arrays, but it should take a similar approach—using indices to “walk down” the two arrays, and making use of the fact that the arrays are sorted. As the elements of the intersection are found, put them in the array that you created at the start of the method.
For full credit:
The intersection that you create should not have any duplicates.
Your algorithm should be as efficient as possible. In particular, you should perform at most one complete pass through each of the arrays.
At the end of the method, return a reference to the array containing the intersection.
Add test code for your method to the main method. Recall that that you can use the Arrays.toString() method to convert an array to a string; import the java.util.package to gain access to the Arrays class.
Here are some expected results:
> int[] a1 = {10, 5, 7, 5, 9, 4}; > int[] a2 = {7, 5, 15, 7, 7, 9, 10}; > int[] result = MergeIntersect.intersect(a1, a2); contents of result: { 5, 7, 9, 10, 0, 0 } > int[] a3 = {0, 2, -4, 6, 10, 8}; > int[] a4 = {12, 0, -4, 8}; > int[] result = MergeIntersect.intersect(a3, a4); contents of result: {-4, 0, 8, 0}Notes:
The array containing the intersection has the same length as the shorter of the original arrays.
When the number of values in the intersection (call it n) is smaller than the length of the shorter array, we end up with extra 0s at the end of the array containing the intersection. This happens because the array of integers that we create is initially filled with 0s, and we only use the first n positions of the array.
Data Structures and Algorithms in Java
ISBN: 978-1118771334
6th edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser