CareerCup

SELECT algorithm for part 2

Yeah, we need to select order statistics for part2 as if K is 2 then selection sort algorithm will take O(n^2) time complexity.

Search on wikipedia for this and you will get how order statistics works.....

"wiki/Selection_algorithm"

I hope it helps........

second part can be done with max heap with k element in it.

can be done in o(k*n) time and o(1) space... obtain the (j+1)th min element by getting the min of all values greater than the jth min value.

private static int quickSelect(int[] a,int p,int r, int i)
{
if(p==r) return p;
int q=randomizedPartition(a, p, r);
int k=q-p+1;
if(i==k)
return q;
else if(i<k)
return quickSelect(a, p, q-1, i);
else
return quickSelect(a, q+1, r, i-k);
}

private static int randomizedPartition(int[] a, int p, int r) {
// TODO Auto-generated method stub
int n = (int)((r-p+1) * Math.random()) ;
n=n+p;
int x = a[n];
a[n]=a[r];
a[r]=x;
return partition(a,p,r);
}

private static int partition(int[] a, int p, int r) {
// TODO Auto-generated method stub
int x = a[r];
int i = p-1;
for(int j=p;j<r;j++)
{
if(a[j]<=x)
{
i=i+1;
int temp = a[j];
a[j]=a[i];
a[i]=temp;
}
}
int temp = a[r];
a[r]=a[i+1];
a[i+1]=temp;
return i+1;
}

private static int quickSelect(int[] a,int p,int r, int i)
	{
		if(p==r) return p;
		int q=randomizedPartition(a, p, r);
		int k=q-p+1;
		if(i==k)
			return q;
		else if(i<k)
			return quickSelect(a, p, q-1, i);
		else
			return quickSelect(a, q+1, r, i-k);
	}

	private static int randomizedPartition(int[] a, int p, int r) {
		// TODO Auto-generated method stub
		int n = (int)((r-p+1) * Math.random())  ;
		n=n+p;
		int x = a[n];
		a[n]=a[r];
		a[r]=x;
		return partition(a,p,r);
	}

	private static int partition(int[] a, int p, int r) {
		// TODO Auto-generated method stub
		int x  = a[r];
		int i  = p-1;
		for(int j=p;j<r;j++)
		{
			if(a[j]<=x)
			{
				i=i+1;
				int temp = a[j];
				a[j]=a[i];
				a[i]=temp;
			}	
		}
		int temp = a[r];
		a[r]=a[i+1];
		a[i+1]=temp;
		return i+1;
	}

One of the best algorithm to find the kth smallest element in the array is to first use a hashmap to count the frequency of every element in the array and then, we will traverse the hashmap and check for the frequency of the numbers if they are greater than 1 then, we will keep reducing the counter of k (which is the kth element we have to find) and when the value of k will be 0 we will print the index which will be our kth smallest element, this is for all distinct element.