使用递归查找 Python 列表中的第 K 个最大元素 [英] Finding the Kth Largest element in a Python List using recursion

问题描述

给定一个包含一些随机未排序数字的输入列表，我正在尝试编写一个程序来输出该列表中第 k 个最大的不同元素.例如:

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

以下函数将列表、主元索引和 k 作为输入，并使用小于主元的所有元素填充列表 "lesser" 并填充另一个列表 "greater" 包含所有大于主元的元素.

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.

现在，查看两个列表的长度，我可以确定第 k 个最大的元素是在较小的列表中还是在较大的列表中.现在我递归地调用相同的函数.但是，对于某些 k 值，我的程序的输出是错误的.

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

推荐答案

有一个简单的方法可以使用递归来解决这个问题.我只是不确定为什么您需要问题描述中的枢轴...例如:

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

这篇关于使用递归查找 Python 列表中的第 K 个最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！