使用递归查找Python列表中第k个最大的元素

Question

给定一个包含一些随机未排序数字的输入列表，我试图编写一个程序，输出该列表中第k个最大的独立元素。例如：

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

下面的函数将列表、透视索引和k作为输入，并用小于透视的所有元素填充list“less”，用大于透视的所有元素填充另一个list“greater”。

现在，看看这两个列表的长度，我可以确定第k个最大的元素是在较小的列表中还是在较大的列表中。现在我递归地调用同一个函数。但是，我的程序的输出对于某些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 1

使用递归有一个简单的方法来解决这个问题。我只是不知道为什么你需要在问题描述的支点。。。例如：

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

Answer 2

有什么理由要使用递归吗？要找到一个列表中第k个最大的元素，您必须查看整个列表，因此问题本质上是O（n）复杂性。

你可以这样做而不用递归：

el = [10, 10, 53, 20, 30, 40, 59, 40]
k = 2

def kth_largest(input_list, k):
    # initialize the top_k list to first k elements and sort descending
    top_k = input_list[0:k]
    top_k.sort(reverse = True)

    for i in input_list[k:]:
        if i > top_k[-1]:
            top_k.pop() # remove the lowest of the top k elements
            top_k.append(i) # add the new element
            top_k.sort(reverse = True) # re-sort the list

    return top_k[-1] # return the kth largest


kth_largest(el, k)

Answer 3

下面是一个简单的解决方案：

def kthmax(k, list):
    if (k == 1):
        return max(list)
    else:
        m = max(list)
        return(kthmax(k-1, [x for x in list if x != m]))

kthmax(3,[4, 6, 2, 7, 3, 2, 6, 6])

输出：4