import java.util.HashSet;
public class Main
{
/*
* BSelect by Blum, Floyd, Pratt, Rivest, Tarjon (1972)
* Written by James Li
* Thanks to professor Will Evans
*/
/*
* Pseudocode:
*
* BSelect(A,k):
* If |A| == 1 return A[1]
* p = GoodPivot(A)
* S = { A[i] | A[i] < p }
* L = { A[i] | A[i] > p }
* If |S| >= k return BSelect(S,k)
* else if |S| == k-1 return p
* else return BSelect(L, k-|S|-1)
*
* GoodPivot(A):
* Divide A into n/5 groups of 5 elements each
* Find the median of each group
* Use BSelect to find the median, p, of the n/5 medians
* Return p
*/
public static void main (String[] args)
{
Integer[] input = { -1,5,8,-3,4,7,2,90 }; //Some arbitrary Integer array
int k = 8;
System.out.println("The " + k + "th largest element in the input is " + BSelect(input, k));
}
/**
* Finds the median of an array in O(n^2) time.
* @param array An array of distinct integers
* @return The median
*/
static int median(Integer[] array)
{
if (array.length == 1)
{
return array[0];
}
int smallerCount = 0;
for (int i = 0 ; i < array.length ; i++)
{
for (int j = 0 ; j < array.length ; j++)
{
if (array[i] < array[j])
{
smallerCount++;
}
}
if (smallerCount == (array.length - 1)/2)
{
return array[i];
}
smallerCount = 0;
}
return -9999; //should never happen
}
/**
* Finds an integer that's somewhat close to the median of array. Runs in O(n) time.
* @param array An array of distinct integers
* @return An integer x in the array such that there are >= array.length/4 values greater than x and >= array.length/4 values less than x
*/
static int GoodPivot(Integer[] array)
{
if (array.length == 1)
{
return array[0];
}
//Divide A into n/5 groups of 5 elements each
int numGroups = array.length / 5;
if (array.length % 5 > 0)
{
numGroups++;
}
Integer[] groupMedians = new Integer[numGroups];
for (int i = 0 ; i < numGroups ; i++)
{
Integer[] subset;
if(array.length % 5 > 0)
{
if (i == numGroups - 1)
{
subset = new Integer[array.length % 5];
}
else
{
subset = new Integer[5];
}
}
else
{
subset = new Integer[5];
}
for (int j = 0; j < subset.length ; j++)
{
subset[j] = array[5*i+j];
}
//Find the median of each group
groupMedians[i] = median(subset);
}
//Use BSelect to find the median, p, of the n/5 medians
int goodPivot = BSelect(groupMedians, groupMedians.length/2 );
return goodPivot;
}
/**
* BSelect by Blum, Floyd, Pratt, Rivest, Tarjon (1972)
* Finds the k-th largest value in array in O(n) time.
* @param array An array with distinct integers.
* @param k A number from 1 to array.length (inclusive)
* @return The k-th largest value in array
*/
static int BSelect(Integer[] array, int k)
{
if (array.length == 1)
{
return array[0];
}
int pivot = GoodPivot(array);
HashSet<Integer> S = new HashSet<Integer>();
HashSet<Integer> L = new HashSet<Integer>();
for (int i = 0; i < array.length ; i++)
{
if (array[i] < pivot)
{
S.add(array[i]);
}
else if (array[i] > pivot)
{
L.add(array[i]);
}
}
if (S.size() >= k)
{
return BSelect(S.toArray(new Integer[0]) ,k);
}
else if (S.size() == k-1)
{
return pivot;
}
else
{
return BSelect(L.toArray(new Integer[0]) , k - S.size() - 1);
}
}
}
0 Comments