在Python中的int列表列表中递归地找到第k个最大的int [英] Recursively find the kth largest int in list of list of int in Python

问题描述

作为编程新手，我正在尝试执行一个函数来查找整数列表中第 k 个最大的整数.我之前尝试过 int 列表并且它起作用了.

As a newbie in programming, I am trying to do a function to find the kth largest int in a list of list of ints. I tried list of ints before and it worked.

然而，对于这个函数，它的基本情况有太多的可能性:

However, for this function, its base case has too many possibilities:

例如:[1, 2], [[], 1], [[1], 2], [[1], [1]]

我陷入了基本情况.任何人都可以给我一个提示吗?

I got stuck at the base case. Can anyone give me a hint for this?

这个函数的操作如下:

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

推荐答案

我编写了一个通用的解决方案(您指定 k)，使用带有默认值的额外参数来跟踪最小的 集合k 到目前为止找到的，以及这是递归的顶级还是子级.子级别返回当前最小的子集，顶级返回最后一个条目(即 k^th 最小值).k 的最小集合使用 heapq 的 nsmallest 方法维护.

I wrote a generalized solution (you specify k) using extra arguments with default values to track both the smallest set of k found so far, and whether this was the top level of the recursion or a sub-level. Sub-levels return the current smallest subset, the top level returns the last entry (which is the k^th smallest value). The smallest set of k is maintained using heapq's nsmallest method.

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

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