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

Question

我需要 python udemy 练习方面的帮助。这是练习：

Write a function, given a list of integers, will give the k smallest integers contained in that list. The algorithm must not change the original array. Make the function as space-efficient as possible, so calling sort or sorted is not allowed. Generalize this to the k-smallest integers, assuming k << n, where n is the number of elements in the list Hint: use a queue.

For example, lowest([1,2,3,-1,-2,-3],2) returns [-3,-2].

我试过这段代码，它适用于 Pycharm 但它不适用于 udemy，它一直给我：

'NoneType' object has no attribute '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

您的功能并不总是 return 列表：

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

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

所以删除 if 块。

其次，当l为空时，你的代码仍然会失败，因为max()的参数必须是non-empty。

不是将 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

然而，应该注意的是，此解决方案在 space 用法上并不比使用 sorted 的解决方案更好。如果你真的想遵循挑战中的限制，这应该不算解决方案。此代码复制整个输入数组，因此使用 O(n) 额外的 space.

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

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

Lowest-k elements using queue. Implementation does not pass test

python

queue