4
\$\begingroup\$

Find the kth largest element in an array of integers. You may assume that:

1 <= k <=size(array).

Any comments? Is there a more efficient solution?

public int findKthLargest(int[] nums, int k) {
    int p = 0;
    int numElements = nums.length;
    // create priority queue where all the elements of nums will be stored
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

    // place all the elements of the array to this priority queue
    for (int n : nums){
        pq.add(n);
    }

    // extract the kth largest element
    while (numElements-k+1 > 0){
        p = pq.poll();
        k++;
    }

    return p;
}
\$\endgroup\$
11
\$\begingroup\$

Here is the median of medians algorithm which also takes \$O(n)\$ in the worst cases:

  1. Divide the array into \$\frac{n}{5}\$ lists of 5 elements each.
  2. Find the median in each sub array of 5 elements.
  3. Recursively find the median of all the medians, let's call it \$M\$.
  4. Partition the array into two sub array 1st sub-array contains the elements larger than \$M\$. Let's say this sub-array is \$a1\$, while other sub-array contains the elements smaller than \$M\$. Let's call this sub-array \$a2\$.
  5. If \$k \le |a1|\$, return selection(a1,k).
  6. If \$k− 1 = |a1|\$, return \$M\$.
  7. If \$k \gt |a1| + 1\$, return selection(a2,k −a1 − 1).

Let's see an interesting example of this where we have to find out the median of unsorted array in linear time. This may sounds NO at first look because median of array is middle element in sorted array if array is of odd length and middle of two middle elements if array is even length.

We can do it using quick/heap sort which takes \$O(nlogn)\$ time, but can we improve? Yes, have you heard about counting sort, which takes \$O(n)\$ time but extra \$O(Max−Min+1)\$ space, where Max and Min are the element of the array?

What if the array is ar[]={10000000,200000000}. Waste of space, right? But if you think about the median, which is nothing but the middle element of the array, where \$k = \frac{n}{2}\$ if array is odd length, can you see anything now? The median is nothing but \$\frac{n}{2}\$th smallest element in the array.

Great, so we got it. We can call median of medians algorithm up to \$k = \frac{n}{2}\$ and we can return ar[n/2] as the median.

Here's the pseudocode for the same:

//selects the median of medians in an array

static int selection(int a[], int s, int e, int k)

{

   // if the partition length is less than or equal to 5

   // we can sort and find the kth element of it

   // this way we can find the median of n/5 partitions

   if(e-s+1 <= 5)

   {

       Arrays.sort(a,s, e);

       return s+k-1;

   }

   /* if array is bigger we partition the array in sub-arrays of size 5
   no. of partitions = n/5 = (e+1)/5 iterate through each partition and
   recursively 
   calculate the median of all of them and keep putting the medians in the 
   starting of the array 
   */

   for(int i=0; i<(e+1)/5; i++)

   { 

      int left = 5*i;

      int right = left + 4;

      if(right > e) right = e;

      //left+(right-left)/2 median will be 3rd element e.g.ar[2] in zero index based array

      int median = selection(a,left, right, 2); 

      swap(a[median], a[i]);

   }

  /*now we have array  a[0] = median of 1st 5 sized partition a[1] = median of 
  2nd 5 sized partition and so on till n/5 to find out the median of these n/5 
  medians we need to select the n/10th element of this set (i.e. middle of it)
 */

   return selection(a, 0, (e+1)/5, ((e+1)/10));

}

Call this function as:

selection(ar,0,ar.length-1,k) //k=n/2 which is median

Analysis of algorithm:

Dividing the array by 5 assures a worst-case split of 70-30 and at-least half of the medians are greater than the median-of-medians, hence at-least half of the \$\frac{n}{5}\$ blocks have at-least 3 elements and this gives a \$\frac{3n}{10}\$ split, which means the other partition is \$\frac{7n}{10}\$ in the worst case. That gives a time complexity of \$T(n) = T(\frac{n}{5}) + T(\frac{7n}{10}) + O(n)\$.

More reading:

\$\endgroup\$
1
  • \$\begingroup\$ Please consider using proper JavaDoc instead of a line-comment. \$\endgroup\$ Jan 2 '17 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.