Iam_Sandeep

Kth Largest element in array

Jun 13th, 2022 (edited)
637
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.98 KB | None | 0 0
  1. class Solution:
  2.     def findKthLargest(self, nums: List[int], k: int) -> int:
  3.         n=len(nums)
  4.         p=random.choice(nums)
  5.         right=[i for i in nums if i>p]
  6.         mid=[i for i  in nums if i==p]
  7.         left=[i for i in nums if i<p]
  8.         L,M=len(left),len(mid)
  9.         if k<=L:
  10.             return self.findKthLargest(left,k)
  11.         elif k>L+M:
  12.             return self.findKthLargest(right,k-L-M)
  13.         else:
  14.             return mid[0]
  15.  '''
  16. If you see this problem in competition, the best way just to sort data and choose k-th largest element in O(n log n) overall complexity. However you can imagine, that it is not the good idea for real interview, where your expected do do something else. There is two classical ways how to find order statistic in linear time (yes, it has its mathematical name):
  17.  
  18.    Median of median approach with worst time complexity O(n), however it is quite painful to code and I do not think anyone expect that you do it.
  19.    So-called Quick Select, which use similar idea to Quick Sort, with average complexity O(n).
  20.  
  21. We are going to discuss Quick Select, because it is easier to code:
  22.  
  23.    First, we need to choose so-called pivot and partition element of nums into 3 parts: elements, smaller than pivot, equal to pivot and bigger than pivot. (sometimes two groups enough: less and more or equal)
  24.    Next step is to see how many elements we have in each group: if k <= L, where L is size of left, than we can be sure that we need to look into the left part. If k > L + M, where M is size of mid group, than we can be sure, that we need to look into the right part. Finally, if none of these two condition holds, we need to look in the mid part, but because all elements there are equal, we can immedietly return mid[0].
  25.  
  26. Complexity: time complexity is O(n) in average, because on each time we reduce searching range approximately 2 times. This is not strict proof, for more details you can do some googling. Space complexity is O(n) as well.
  27. '''
  28.        
Add Comment
Please, Sign In to add comment