class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
tmp = MyQueue()
for i in range(k):
tmp.push(nums[i])
res.append(tmp.front())
for j in range(k, len(nums)):
tmp.pop(nums[j-k])
tmp.push(nums[j])
res.append(tmp.front())
return res
class MyQueue:
from collections import deque
def __init__(self):
self.queue = deque() # 这里使用 list 会超出限制
def pop(self, val):
if self.queue and val == self.queue[0]:
self.queue.popleft()
def push(self, val):
while self.queue and val > self.queue[-1]:
self.queue.pop()
self.queue.append(val)
def front(self):
return self.queue[0]
list
是Python内置的动态数组类型,它可以存储任意类型的对象,并且可以根据需要动态调整大小。list
具有灵活的索引、切片和操作方法,可以方便地进行元素的插入、删除和修改。然而,当需要从列表的头部频繁地插入和删除元素时,list
的性能可能会较低,因为这涉及到移动其他元素的操作。
deque
(Double-ended Queue,双端队列)是Python标准库collections
模块中提供的数据结构。它是一个双端队列,支持从队列的两端高效地进行插入和删除操作。与list
相比,deque
在执行头部操作(插入和删除)时具有更高的性能,因为它使用了一种双向链表的数据结构。如果你需要在列表的两端频繁地进行插入和删除操作,那么使用deque
可能会更高效。
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
res = []
a_map = {}
for i in nums:
a_map[i] = a_map.get(i, 0) + 1
min_heap = []
for key, val in a_map.items():
heapq.heappush(min_heap, (val, key))
if len(min_heap) > k:
heapq.heappop(min_heap)
for j in range(k-1, -1, -1):
res.append(heapq.heappop(min_heap)[1])
return res
Python提供了heapq模块,其中包含了对堆操作的支持。通过heapq模块,可以轻松地创建和操作堆数据结构,包括插入元素、删除元素、获取最小(或最大)元素等操作。
下面是一个简单的示例,展示了如何使用heapq模块来创建和操作堆:
import heapq
# 创建一个空的堆
heap = []
# 向堆中插入元素
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
# 从堆中弹出最小元素
min_element = heapq.heappop(heap)
print(min_element) # 输出: 1
# 获取堆中最小元素(不弹出)
min_element = heap[0]
print(min_element) # 输出: 3
# 将列表转换为堆
my_list = [9, 2, 6, 4, 8]
heapq.heapify(my_list)
print(my_list) # 输出: [2, 4, 6, 9, 8]
标签:queue,heapq,min,self,list,Pyhton,347,heap,第十三天
From: https://www.cnblogs.com/yixff/p/17783423.html