Radk7 Radk7 - 1 year ago 62
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:

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:
elif x < pivot:
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
return kthLargest(greater, g - 1, k) #Else kth largest element is in greater list

Answer Source

There's an easy way to do this problem using recursion. I'm just not sure why you need the pivot in the problem description... For example:

def find_kth(k, arr):
    if k == 1:
        return max(arr)
    m = max(arr)
    new_arr = list(filter(lambda a: a != m, arr))
    return(find_kth(k-1, new_arr))