python - 我可以维护一个元组列表(时间戳、ID)，部分排序时间小于线性时间吗？

Question

约束是:

• 输入是一个元组流(时间戳，id)
• id 并不是普遍唯一的，因此重复项可能会随机来自流
• 时间戳也不是唯一的，也是随机的
• 输出必须是一个长度为 k 的列表，其中 k 很小(大约 50)并且列表中的每个项目都是(时间戳，ids)的元组。返回列表中的 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() 函数。