使用队列的最低 k 个元素。实施未通过测试

Question

我需要 python udemy 练习方面的帮助。这是练习：编写一个函数，给定一个整数列表，将给出该列表中包含的 k 个最小整数。该算法不得更改原始数组。使函数尽可能节省空间，因此不允许调用 sort 或排序。将其推广到 k 个最小整数，假设 k << n，其中 n 是列表中的元素数量 提示：使用队列。例如，lower([1,2,3,-1,-2,-3],2) 返回 [-3,-2]。我尝试了这段代码，它在 Pycharm 上工作，但在 udemy 上不起作用，它一直给我：“NoneType”对象没有属性“sort”。class Node:    def __init__(self, data=None, next_node=None):        self.data = data        self.next = next_node    def __str__(self):        return str(self.data)class Queue:    def __init__(self):        self.length = 0        self.head = None        self.last = None    def enqueue(self, data):        node = Node(data)        if self.length == 0:            self.head = node            self.last = node            self.length = 1            return        last = self.last        last.next = node        self.last = node        self.length += 1    def dequeue(self):        if self.length == 0:            return None        data = self.head.data        self.head = self.head.next        self.length -= 1        if self.length == 0:            self.last = None        return datadef lowest(l, k):    if k >= (len(l)//2):        return    q = Queue()    array = l.copy()    while True:        temp = max(array)        q.enqueue(temp)        array.remove(temp)        if len(array) == k:            return arrayl = [1, 2, 3, -1, -2, -3]print(lowest(l, 2))l = [32,21,45,74,24,65,34,54,78,98,77,89,84]print(lowest(l,9))

Answer 1

您的函数并不总是返回列表：

if k >= (len(l)//2):

    return

中的条件if可能为真，然后返回None。例如，如果l为空（因此k为零），则此条件将为 true，并且您的代码返回None而不是预期的[].

所以删除那个if块。

其次，当l为空时，您的代码仍然会失败，因为 的参数max()必须非空。

不要if在循环内部放置一个确定循环何时结束的方法，而是将条件放在条件中while：

def lowest(l, k):

    q = Queue()

    array = l.copy()

    while k < len(array):

        temp = max(array)

        q.enqueue(temp)

        array.remove(temp)

    return array

但应该注意的是，该解决方案在空间使用方面并不比使用sorted. 如果您确实想遵循挑战中的限制，那么这不应算作解决方案。此代码复制整个输入数组，因此使用O(n)额外空间。

有一些方法可以只使用O(k)额外空间，即返回结果所需的空间。尽管挑战的描述暗示使用队列，但我会选择永远不会超过k 个条目的最大堆。