CareerCup

what is rank k number of an array...

public class KRankService
{
	public static void kRank(int[] arr, int k)throws NullPointerException, IllegalArgumentException
	{
		if(arr==null)
		{
			throw new NullPointerException(“input array cannot be null”);
		}
		if(k<0||k>arr.length)
		{
			throw new IllegalArgumentException(“k cannot be less than zero or greater than array length”);
		}
		
		MinHeap mh=new MinHeap(k);
		HashMap<Integer,Boolean> inHeap=new HashMap<Integer,Boolean>(k);
		for(int i=0; i< arr.length;i++)
		{
			if(!inHeap.contains(arr[i]))
			{
				if(mh.isFull())
				{
					if(arr[i]>mh.getMin())
					{
						mh.extractMin();
					}
				}
				mh.insert(arr[i]);
				inHeap.put(arr[i],true);
				
			}
				
		}
			
		
		System.out.println(“kth rank: “ + mh.getMin());
		System.out.println(“k highest values: “ );
		while(!mh.isEmpty())
		{
			System.out.print(mh.extractMin() + “ “);
		}
	
	}
	private static int[] getInputArray(int n)
	{
	 	if(n==0)
		{
			return null;
		}
		int[] arr=new int[n];
		Random rnd=new Random();
		for(int i=0; i<arr.length;i++)
		{
			arr[i]=rnd.nextInt(n);
		}
		return arr;
	}
	public static void main(String[] args)
	{
		Random rnd=new Random();
		int n=rnd.nextInt(1001);
		int k=rnd.nextInt(51);
		int[] input=KRankService.getInputArray(n);
		KRankService.kRank(input,k);
	}
}

We could also use randomised quick sort n partition about kth element.

#include <iostream>
#include <map>

using namespace std;

void arr_rank(int a[], int n)
{
  map <int, int> count;
  map <int, int> rank;
  
  int rankCount = 1;
  
  // construct map
  for(int i=0;i<10;i++)
  {
    count[i] = 0;
    rank[i] = 0;
  }
  
  for(int i=0;i<n;i++)
  {
    count[a[i]] += 1;
  } 
  
  for (int i=0;i<10;i++)
  {
    if (count[i] > 0)
    {
      rank[i] = rankCount;    
      rankCount++;
    }
  }
  
  for (int i=0;i<n;i++)
    cout << rank[a[i]] << endl;

}

int main(void)
{
  int a[] = {3, 1, 3, 4, 9, 8, 5};
 
  arr_rank(a, 7);
  
}

why can't we use bubble sort k times : Time complexity : O(nk)
Extra Space : O(1)

Since sorting using bubble sort will be in O(nK) while using min Heap will be NLogK
so prefer MinHeap to BubbleSort

We can use MinHeap and before inserting into MinHeap , we have to check whether this number exists as we can not use the hash due to the constrain of time complexity

Space => O(k) which can refer as O(1)
Time => O(nk) which can refer as O(n)