序列插入删除元素collections.deque

74 阅读 0 评论 49 点赞

我是靠谱客的博主从容月饼，最近开发中收集的这篇文章主要介绍序列插入删除元素collections.deque，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

小云正在参与开发一个即时聊天工具，他负责其中的会话列表部分。
会话列表为显示为一个从上到下的多行控件，其中每一行表示一个会话，每一个会话都可以以一个唯一正整数id表示。
当用户在一个会话中发送或接收信息时，如果该会话已经在会话列表中，则会从原来的位置移到列表的最上方；如果没有在会话列表中，则在会话列表最上方插入该会话。
小云在现在要做的工作是测试，他会先把会话列表清空等待接收信息。当接收完大量来自不同会话的信息后，就输出当前的会话列表，以检查其中是否有bug。

输入描述:

输入的第一行为一个正整数T（T<=10），表示测试数据组数。
接下来有T组数据。
每组数据的第一行为一个正整数N（1<=N<=200），表示接收到信息的次数。
第二行为N个正整数，按时间从先到后的顺序表示接收到信息的会话id。会话id不大于1000000000。

输出描述:

对于每一组数据，输出一行，按会话列表从上到下的顺序，输出会话id。
相邻的会话id以一个空格分隔，行末没有空格。

输入例子1:

3
5
1 2 3 4 5
6
1 100 1000 1000 100 1
7
1 6 3 3 1 8 1

输出例子1:

5 4 3 2 1
1 100 1000
1 8 3 6

我的解答：

def game(one_n, req):
    one_n = int(one_n)
    req = req.split(' ')
    req_reverse = req[::-1]
    del_index = []
    while one_n:
        if req_reverse[one_n-1] in req_reverse[:one_n-1]:
            del_index.append(one_n-1)
        one_n -= 1
    res = []
    for i in range(len(req_reverse)):
        if i not in del_index:
            res.append(req_reverse[i])
    return ' '.join(res)

n = input()
for i in range(int(n)):
    one_n = input()
    req = input()
    print(game(one_n, req))

以下解答来源：牛客网

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

# 链接：https://www.nowcoder.com/questionTerminal/0f52adb3946249f9bb63d964658b2691?answerType=1&f=discussion
# 来源：牛客网

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))