<p>给定一个包含一些随机未排序数字的输入列表,我试图编写一个程序,输出该列表中第k个最大的独立元素。例如:</p>
<pre><code>Input:
el = [10,10, 20,30,40, 40]
k = 2
Output: 30 #Since 30 is the second largest distinct element in the list
</code></pre>
<p>下面的函数将列表、透视索引和k作为输入,并用小于透视的所有元素填充list<em>“less”</em>,用大于透视的所有元素填充另一个list<em>“greater”</em>。</p>
<p>现在,看看这两个列表的长度,我可以确定第k个最大的元素是在较小的列表中还是在较大的列表中。现在我递归地调用同一个函数。但是,我的程序的输出对于某些k值是错误的</p>
<pre><code>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.<a href="https://www.cnpython.com/list/append" class="inner-link">append</a>(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
</code></pre>
<p>使用递归有一个简单的方法来解决这个问题。我只是不知道为什么你需要在问题描述的支点。。。例如:</p>
<pre><code>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))
</code></pre>