使用队列的最低 k 元素.实施未通过测试 [英] Lowest-k elements using queue. Implementation does not pass test

问题描述

我需要有关 Python udemy 练习的帮助.这是练习:

I need help with a python udemy exercise. This is the exercise:

写一个函数，给定一个整数列表，将给出k个最小的该列表中包含的整数.算法不能改变原始数组.使函数尽可能节省空间，因此不允许调用 sort 或 sorted.将此概括为k-最小整数，假设k＜＜n，其中 n 是列表中的元素提示:使用队列.

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.

例如，lowest([1,2,3,-1,-2,-3],2) 返回 [-3,-2].

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

我试过这段代码，它在 Pycharm 上工作，但在 udemy 上不起作用，它一直给我:

I tried this code and it works on Pycharm but it doesn't work on udemy and it keeps giving me:

'NoneType' 对象没有属性 'sort'.

'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))

推荐答案

你的函数并不总是返回一个列表:

Your function is not always returning a list:

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

if 中的条件可能为真，然后返回 None.例如，如果 l 为空(结果 k 为零)，则此条件为真，您的代码返回 None 而不是预期 [].

The condition in the if might be true, and then you return None. For instance, if l is empty (and by consequence k is zero), this condition will be true and your code returns None instead of the expected [].

所以删除那个 if 块.

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

Secondly, your code will still fail when l is empty, because the argument of max() must be non-empty.

与其将 if 放在决定循环何时结束的循环中，不如将条件放在 while 条件中:

Instead of putting an if inside the loop that determines when the loop should end, put the condition in the while condition:

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) 额外空间.

It should be noted however, that this solution is no better in space usage than a solution that would use sorted. If you really want to follow the restrictions in the challenge, this should not count as a solution. This code copies the whole input array, and so uses O(n) extra space.

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

There are ways to only use O(k) extra space, which is the space needed to return the result. Although the description of the challenge hints to use a queue, I would opt for a max heap which never exceeds k entries.

这篇关于使用队列的最低 k 元素.实施未通过测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！