会话列表

当用户在一个会话中发送或接收信息时，如果该会话已经在会话列表中，则会从原来的位置移到列表的最上方；如果没有在会话列表中，则在会话列表最上方插入该会话。

其实就是一个长度无限的 LRU 列表，第一次出现就插入到列表头部，否则先从列表中删除在插入到列表头部。使用 deque 而不使用 list 是因为 list 在头部插入元素的复杂度是 ，而 deque 在两端插入和删除的复杂度都是 。

from collections import deque


def process(id_li):
    has_seen = set()
    q = deque()
    output = []
    for this_id in id_li:
        if this_id not in has_seen:  # 如果第一次出现
            has_seen.add(this_id)    # 加入 has_seen 方便查找
            q.appendleft(this_id)    # 添加到队首
        else:                        # 已经出现过
            q.remove(this_id)        # 移除旧元素
            q.appendleft(this_id)    # 添加到队首
    while q:
        output.append(q.popleft())
    outputs.append(output)


if __name__ == '__main__':
    T = int(input().strip())
    outputs = []
    for group_i in range(T):
        N = int(input().strip())
        id_li = input().split()
        process(id_li)

    for output in outputs:
        print(' '.join(output))