Python中的多集

Question

我正在CSES上处理这个问题，红绿灯：

有一条长度为的街道，其位置编号为0,1。最初没有红绿灯，但有几组红绿灯被一个接一个地添加到街道上。

你的任务是计算没有每次添加后的红绿灯。

输入

第一个输入行包含两个整数和：街道和交通灯组的数量。

然后，下一行包含n个整数₁，₂…，：每组交通灯。每个位置都是不同的。

输出

打印之后没有红绿灯的最长通道的长度每次添加。

限制

• 1≤≤10⁹
• 1≤≤2·10⁵
• 0<<

示例

输入：

8 3
3 6 2

输出：

5 3 3

因此，为了有效地解决这样的问题，我需要Python中类似于列表的数据结构，但元素的搜索和删除需要为O(1)或者更像类似于集合的数据结构，但我需要能够插入多个相同的元素并保持顺序。我的问题代码是：

from collections import defaultdict
from bisect import bisect_right , insort
x , n = list(map(int  , input().split()))
arr = list(map(int , input().split()))
lens = defaultdict(int)
lens[x] = 1
lights = [0,x]
for ele in arr:
idx = bisect_right(lights , ele)
to_be_removed = lights[idx] - lights[idx-1]
lens[to_be_removed] -= 1
lens[lights[idx]-ele] += 1
lens[ele-lights[idx-1]] += 1
insort(lights , ele)
print(max([x for x in lens.keys() if lens[x]])  , end =" ") 

但是，此代码速度较慢。c++中有一种称为多集的数据结构。但是在python中找不到类似的数据结构。感谢您的帮助。

Answer 1

lens的数据结构类似于多集，也可用作Counter。在时间复杂性方面，你的算法的瓶颈是：

max([x for x in lens.keys() if lens[x]]) 

这是一个具有线性时间复杂性的运算，因此它使算法具有二次性。

为了改进算法的这一部分，我建议使用堆。heapq提供了一个最小堆实现。由于你实际上需要一个最大堆，你只需要用负长度来填充它。

其次，insort也具有线性时间复杂度(尽管使用的时间比上面的max()表达式少)。您可以通过使用自平衡搜索树实现来改进这一点，该实现没有标准库，但有一些库提供排序列表，如sortedcontainers。

以下是如何调整代码以实现这两个想法：

from collections import defaultdict
from heapq import heappush, heappop
from sortedcontainers import SortedList
x , n = list(map(int  , input().split()))
arr = list(map(int , input().split()))
lens = defaultdict(int)
lens[x] = 1
lights = SortedList([0, x])  # For faster insertion
heap = [-x]  # Put total width also in a heap
for ele in arr:
idx = lights.bisect_right(ele)
to_be_removed = lights[idx] - lights[idx-1]
lens[to_be_removed] -= 1
# Add widths to the heap when they are the only occurrences
right = lights[idx]-ele
if lens[right] == 0:
heappush(heap, -right)
lens[right] += 1
left = ele-lights[idx-1]
if lens[left] == 0:
heappush(heap, -left)
lens[left] += 1
# Remove the largest width as long as it no longer represents a segment
while lens[-heap[0]] == 0:
heappop(heap)

# The add method is O(logn)
lights.add(ele)
# Just output the largest width in the heap
print(-heap[0], end = " ")