我可以维护一个元组列表吗?(时间戳，id)，在不到线性的时间内部分排序

Question

约束是：

• 输入是元组流(时间戳，id(
• id并不是普遍唯一的，因此重复项可能会随机从流中出现
• 时间戳也不是唯一的，也是随机的
• 输出必须是一个长度为k的列表，其中k很小(大约50(，并且列表中的每个项都是一个元组(时间戳，id(。返回列表中的id必须是列表中其他id唯一的，时间戳必须是输入流中最新的50

我的想法是使用映射和堆，但我提出的任何解决方案都使用线性时间。

Answer 1

您可以使用sort((函数，我从https://www.programiz.com/python-programming/methods/list/sort

# take second element for sort
def takeSecond(elem):
return elem[1]
# random list
random = [(2, 2), (3, 4), (4, 1), (1, 3)]
# sort list with key
random.sort(key=takeSecond)
# print list
print('Sorted list:', random)
Output
Sorted list: [(4, 1), (2, 2), (1, 3), (3, 4)]

对于重复的id，可以在列表中插入元组时使用map((函数。