Radk7 - 1 year ago 62

Python Question

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

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

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))
```