使用队列的最低 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 data

def 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 array

l = [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):&nbsp; &nbsp; return中的条件if可能为真，然后返回None。例如，如果l为空（因此k为零），则此条件将为 true，并且您的代码返回None而不是预期的[].所以删除那个if块。其次，当l为空时，您的代码仍然会失败，因为 的参数max()必须非空。不要if在循环内部放置一个确定循环何时结束的方法，而是将条件放在条件中while：def lowest(l, k):&nbsp; &nbsp; q = Queue()&nbsp; &nbsp; array = l.copy()&nbsp; &nbsp; while k < len(array):&nbsp; &nbsp; &nbsp; &nbsp; temp = max(array)&nbsp; &nbsp; &nbsp; &nbsp; q.enqueue(temp)&nbsp; &nbsp; &nbsp; &nbsp; array.remove(temp)&nbsp; &nbsp; return array但应该注意的是，该解决方案在空间使用方面并不比使用sorted. 如果您确实想遵循挑战中的限制，那么这不应算作解决方案。此代码复制整个输入数组，因此使用O(n)额外空间。有一些方法可以只使用O(k)额外空间，即返回结果所需的空间。尽管挑战的描述暗示使用队列，但我会选择永远不会超过k 个条目的最大堆。