Find common numbers in arrays: Part 3
Print This Post
Reminder: out problems are
- How to find the first common integer in two pre-sorted array
- How to find the first common integer in two unsorted array
- How to find all the common numbers in two pre-sorted array
- How to find all the common numbers in two unsorted array
- How to find all the common numbers in three pre-sorted array
- How to find all the common numbers in three unsorted array
- Finally, here is the problem that this series of posts are gonna discuss: How to find all the common numbers in n unsorted arrays
Speaking of the 2nd, 4th and 6th problem, we can either achieve O(n lg n) running time by sorting the array first then perform the operations discussed in previous posts, or we can take advantage of a Set to determine whether the element has presented or not and achieve linear running time with linear space complexity.
Now, here is the generalized solution for the 7th problem: How to find all the common elements in n unsorted arrays. Basically, the logic for the program is to maintain an array pool which was implemented as a HashMap mapping from the array to an Integer which will be used as its pointer. You can add an array into the object, or you can specify a List of arrays. While adding an array to the pool, the program will first check if the array has been sorted in ascending order, if not, using a quick sort to sort it then add it to the pool. At any time, you can use getCommonElements() function which returns an ascending array of common elements among all the arrays in the pool.
The code is pretty much simple, the getCommonElements() is the bottommost function.
/**
* Author: I-Fan Chu
* Blog: http://blog.ifanchu.com
* Date: May 1, 2010
*/
package com.ifanchu.util;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.io.PrintStream;
import com.ifanchu.algorithm.sorting.AbstractSorter;
import com.ifanchu.algorithm.sorting.QuickSort;
/**
* This class is to represent a mechanism to find all the common elements in
* several arrays.
*/
public class CommonNumbers<T> {
/**
* If the generic type does not implement <tt>Comparable</tt>, this <tt>Comparator</tt>
* needs to be specified.
* If the generic type has implemented <tt>Comparable</tt>, and this <tt>Comparator</tt>
* has also been specified, the comparison will be performed based on the Comparator
*/
private Comparator<T> comp;
/**
* A pointer array, provide one pointer for each array in <tt>pool</tt>
*/
private transient Map<T[], Integer> pointers;
/**
* A sorter in case the given array is not in ascending order hence needs sort
*/
private AbstractSorter<T> sorter;
/************************************
* Constructors *
***********************************/
/**
* Default constructor
*
* @param list The given <tt>List</tt> of array, could be null
* @param comp The given <tt>Comparator</tt>, could be null
*/
public CommonNumbers(List<T[]> list, Comparator<T> comp){
pointers = new HashMap<T[], Integer>();
appendArrays(list);
this.comp = comp;
}
public CommonNumbers(List<T[]> list){
this(list, null);
}
public CommonNumbers(){
this(null, null);
}
/************************************
* Getters and Setters *
***********************************/
public Comparator<T> getComp() {
return comp;
}
public void setComp(Comparator<T> comp) {
this.comp = comp;
}
/************************************
* Helper Methods *
***********************************/
/**
* An internal compare method to perform comparison between two given object,
* if the <i>comp</t> has been specified, based on it; if not, the generic type
* must have implemented <tt>Comparable</tt> and this operations will then be
* performed based on it; otherwise, throw exception.
*
* @param t1 The first element to be compared
* @param t2 The second element to be compared
* @return An integer to indicate the result of comparison between <i>t1</i> and <i>t2</i>.
* If t1>t2, return a positive number; if t1<t2, return a negative number;
* return 0 if they are considered equal.
* @throws IllegalArgumentException If neither the <i>comp</i> has been specified nor the generic
* type did not implement <tt>Comparable</tt>
*/
protected int compare(T t1, T t2){
if(comp != null){
return comp.compare(t1, t2);
}else{
if(t1 instanceof Comparable<?> && t2 instanceof Comparable<?>){
return ((Comparable<T>) t1).compareTo(t2);
}else{
throw new IllegalArgumentException("The generic type must either implement Comparable" +
" or a customized Comparator be specified.");
}
}
}
/**
* A public helper method to varify if the given arr is in ascending order.
*
* @param arr The given array with generic type T
* @return true if the order is ascending; false otherwise
* @throws NullPointerException If the given array is <i>null</i>
*/
protected boolean isSorted(T[] arr){
if(arr==null || arr.length<=0)
throw new NullPointerException("The given array can not be null");
//an 1-element array is considered in ascending order
if(arr.length==1)
return true;
for(int i=0; i<arr.length-1; i++){
if(compare(arr[i], arr[i+1])>0)
return false;
}
return true;
}
/**
* Perform an quick sort to the given array. Noted that the original
* array in the pool will be compromised.
*
* @param arr The array needs to be sorted
* @return A sorted array
* @throws NullPointerException If the given array is <tt>null</tt>
*/
protected T[] sortInAscending(T[] arr){
if(arr==null)
throw new NullPointerException();
if(arr.length == 0 || arr.length == 1)
return arr;
sorter = new QuickSort<T>(arr);
if(comp!=null)
sorter.setComp(comp);
assert(arr.length==sorter.getArray().length);
sorter.sort();
return sorter.getArray();
}
/**
* Append another array to the pool for comparison
*
* @param arr The array that needs to be added to the pool
* @throws NullPointerException if the given array is <i>null</i> or length is 0
*/
public void appendArray(T[] arr){
if(arr==null || arr.length==0)
throw new NullPointerException();
if(!isSorted(arr))
arr = sortInAscending(arr);
pointers.put(arr.clone(), 0);
}
/**
* Append a List of arrays to the pool
*
* @param list A <tt>List</tt> of arrays
*/
public void appendArrays(List<T[]> list){
if(list==null || list.size()==0)
return;
for(T[] arr: list)
appendArray(arr);
}
/**
* Internal method to check if the pointers haven't reached the length of its
* corresponding array length
*
* @param arr The array that needs to be checked if the pointer has reached its
* length or not
* @return true if the pointer hasn't reach its corresponding array length
* @throws NullPointerException if the given array is null
*/
private boolean underThreshold(T[] arr){
if(arr==null)
throw new NullPointerException();
return pointers.get(arr).intValue()<arr.length-1;
}
/**
* Internal method performs sequential search from the current value of its pointer.
* The value of the pointer will be incremented if <i>target</i> is larger than the element
* currently pointed by pointer.
*
* @param arr The array under operation
* @param target The search target
* @return true is found, pointer will be updated to the position;
* false otherwise
* @throws NullPointerException if either arr or target is null
*/
private boolean findNextCommon(T[] arr, T target){
if(arr==null || target==null)
throw new NullPointerException();
int index = pointers.get(arr);
while(underThreshold(arr) && compare(arr[index], target)<0){
pointers.put(arr, ++index);
}
if(compare(arr[index], target)==0)
return true;
return false;
}
/**
* Find the next common element from the two given array.
* The corresponding pointers will be updated along with operation proceeds
*
* @param arr1
* @param arr2
* @return the common element is found; null otherwise
* @throws NullPointerException if either of the two given arrays is null
*/
private T findNextCommon(T[] arr1, T[] arr2){
if(arr1==null || arr2==null)
throw new NullPointerException();
int i = pointers.get(arr1);
int j = pointers.get(arr2);
while(i<arr1.length && j<arr2.length){
int dif = compare(arr1[i], arr2[j]);
if(dif<0)
pointers.put(arr1, i++);
else if(dif>0)
pointers.put(arr2, j++);
else{
T temp = arr1[i];
pointers.put(arr1, ++i);
pointers.put(arr2, ++j);
return temp;
}
}
return null;
}
/**
* Debug use
*
* @param out
*/
public void printAllArrays(PrintStream out){
if(pointers==null || pointers.size()==0)
return;
for(T[] arr: pointers.keySet()){
out.print("{");
for(T t:arr)
out.print(t.toString() + (t!=arr[arr.length-1]? ",":""));
out.println("}");
}
}
/**
* Retuen a <tt>List</tt> which contains all the arrays in the pool
*
* @return A <tt>List</tt> which contains all the arrays in the pool
* @throws NullPointerException If the <i>pointers</i> is null
* @throws NoSuchElementException If there is no array exists in the pool
*/
protected List<T[]> getArrayList(){
if(pointers==null)
throw new NullPointerException("Pool is null");
if(pointers.size()==0)
throw new NoSuchElementException("Pool is empty");
List<T[]> list = new ArrayList<T[]>();
list.addAll(pointers.keySet());
return list;
}
/************************************
* Main Operations *
***********************************/
public List<T> getCommonElements(){
//if the pool size less than or equal to 1, no common elements
if(pointers.size()<=1)
throw new IllegalArgumentException("There should be at least two arrays");
List<T> buffer = new ArrayList<T>();
//arbitratrily pick two array from the pool
List<T[]> pool = getArrayList();
T[] arr1 = pool.get(0);
T[] arr2 = pool.get(1);
T temp;
while((temp=findNextCommon(arr1, arr2))!=null){
boolean flag = true;
for(T[] arr: pool){
if(arr==arr1 || arr==arr2)
continue;
if(!findNextCommon(arr, temp)){
flag = false;
break;
}
}
if(flag)
buffer.add(temp);
}
return buffer;
}
}
Please leave comments if there is any mistake or improvement or question. Thank you very much.
Clap
Loading ...