Radk7 - 1 year ago 129

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

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**