我需要 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))
1 回答
蕭十郎
TA貢獻1815條經驗 獲得超13個贊
您的函數并不總是返回列表：
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 個條目的最大堆。
添加回答
舉報
0/150
提交
取消