Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Algorithm to return kth largest number

By: indushree-kumar on Jul 24th, 2012  |  syntax: None  |  size: 0.71 KB  |  hits: 14  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. kthLargest(A, k)
  2.   let r be a random number in the range 1 to length(A)
  3.   let num = A[r]
  4.   let A1, A2 be new arrays
  5.   /*split the given numbers into a array A1 of small numbers and A2 of big numbers*/
  6.   for i = 1 to n
  7.     if A[i] < k then
  8.       append A[i] to A1
  9.     else if A[i] > k then
  10.       append A[i] to A2
  11.   end for
  12.   if k <= length(A1):
  13.     /*it's in the pile of small elements*/
  14.     return kthLargest(A1, k) /*recursively call kthLargest*/
  15.   else if k > length(A) - length(A2)
  16.     /*it's in the pile of big elements*/
  17.     return kthLargest(A2, k - (length(A) - length(A2))  /*recursively call kthLargest*/
  18.   else
  19.     /*it's equal to the num*/
  20.     return num
  21.  
  22. The complexity of this algorithm is O(n).
create a new version of this paste RAW Paste Data