Radk7 - 1 year ago 155
Python Question

# Finding the Kth Largest element in a Python List using recursion

Given an input list that contains some random unsorted numbers, I am trying to write a program that outputs the kth largest distinct element in that list. For example:

``````Input:
el = [10,10, 20,30,40, 40]
k = 2
Output: 30 #Since 30 is the second largest distinct element in the list
``````

The following function, takes as input a list, the pivot Index and k and populates list "lesser" with all elements lesser than the pivot and populates another list "greater" with all elements greater than the pivot.

Now, looking at the length of the two list, I can determine if the kth largest element is in the lesser list or the greater list. Now I recursively call the same function. However, my program's output is wrong for certain values of k.

``````def kthLargest(el, pivotIndex, k):
pivot = el[pivotIndex]
lesser = [] #List to store all elements lesser than pivot
greater = [] #Lsit to store all elements greater than pivot
equals = [] #List to store all elements equal to pivot

for x in el:
if x > pivot:
greater.append(x)
elif x < pivot:
lesser.append(x)
else:
equals.append(x)
g = len(greater) #Length of greater list
l = len(lesser)

if(g == k - 1): #If greater list has k-1 elements, that makes the pivot kth largest element
return pivot
elif(g < k):
return kthLargest(lesser, l - 1, k) #If greater list is smaller than k, kth largest element is in lesser list
else:
return kthLargest(greater,  g - 1, k) #Else kth largest element is in greater list
``````

``````def find_kth(k, arr):