以遞歸方式在Python中找到列表中第k個最大的int

Question

作爲編程中的新手，我試圖做一個函數來查找ints列表中的第k個最大的int。我之前嘗試過整套清單，它工作正常。

然而，對於這個功能，它的基本情況有太多的可能性：

例：[1, 2], [[], 1], [[1], 2], [[1], [1]]

我被困在基本情況。任何人都可以給我一個提示嗎？

此功能將操作，如：

find_2smallest([1,1,3])->1 
find_2smallest([[1,[]], 9, [[1], [3]], [4]])->3 

Answer 1

我寫了一個廣義的解決方案（您指定k）使用額外的參數與默認值跟蹤到目前爲止發現的最小集合k，以及這是最高級別的遞歸還是子級別。子級返回當前最小的子集，頂級返回最後一個條目（即最小值）。使用heapq的nsmallest方法維護最小的一組k。

import heapq 

def find_kth_smallest(k, a_list, smallest_k = [], top_level = True): 
    l = len(a_list) 
    if l > 1: 
     l /= 2 
     smallest_k = find_kth_smallest(k, a_list[:l], smallest_k, False) 
     smallest_k = find_kth_smallest(k, a_list[l:], smallest_k, False) 
    elif l < 1: 
     return [] 
    else: 
     if isinstance(a_list[0], list): 
      smallest_k = find_kth_smallest(k, a_list[0], smallest_k, False) 
     else: 
      smallest_k.append(a_list[0]) 
      smallest_k = heapq.nsmallest(k, smallest_k) 
    if top_level: 
     return smallest_k[-1] 
    else: 
     return smallest_k 

print find_kth_smallest(3, [10, [9, 8, [[]]], [7, 6, [[5], 4, 3]], 2, 1]) # => 3 

Answer 2

一些提示：

寫一個扁平化的功能列表層次結構轉換爲一個單一的集合（具有唯一的要素），排序並挑選第k元素。

樣本實現

def flatten(t): 
    for e in t: 
     if isinstance(e,list): 
      yield from flatten(e) 
     else: 
      yield e 



set(flatten([[1,[]], 9, [[1], [3]], [4]])) 

{1, 3, 4, 9} 

當然

，這種方法是不是最有效的（也許這是效率最低的）。您可以返回每個子級別的前k個元素，並在每次合併時在第k級別修剪。