如何按元素最后出现位置对列表排序？求高效实现方案

给定列表：

list_ = ['a', 'b', 'c', 'a', 'a', 'c']

需求为：去重后按元素最后出现时间从早到晚排序——即最早完成最后一次出现的元素排在最前，最晚完成最后一次出现的元素排在最后，最终结果如下：

final = ['b', 'a', 'c']  # 'b'最后出现时间最早，'c'最晚

当前采用的实现方案：

list_ = list_[::-1]
list_ = [*dict.fromkeys(list_)][::-1]

但当列表规模极大时，两次反转操作会产生额外的内存开销与时间成本，因此需要更高效的实现方式，是否存在基于deque的高效处理方法？

基于deque的高效实现方案 #

核心思路是追踪元素的最后出现位置，同时维护有序的去重结果，deque的双向操作特性可以很好地适配这个需求，配合哈希结构实现快速判断与定位：

基础版实现 #

遍历原列表，用集合记录已加入结果的元素，用deque存储最终序列：

• 遇到未记录的元素：添加到deque末尾并标记为已见
• 遇到已记录的元素：从deque中移除该元素，再重新添加到末尾（更新其为最后出现的顺序）

代码如下：

from collections import deque

list_ = ['a', 'b', 'c', 'a', 'a', 'c']
seen = set()
result = deque()

for item in list_:
    if item in seen:
        result.remove(item)
    else:
        seen.add(item)
    result.append(item)

final = list(result)
print(final)  # 输出: ['b', 'a', 'c']

优化版（O(n)时间复杂度） #

基础版中deque.remove(item)是O(k)操作（k为当前deque长度），如果列表重复元素极多，可通过字典记录元素在deque中的索引，直接定位删除，将操作复杂度降至O(1)：

from collections import deque

list_ = ['a', 'b', 'c', 'a', 'a', 'c']
seen = dict()  # 键：元素，值：元素在deque中的索引
result = deque()

for item in list_:
    if item in seen:
        # 删除旧位置的元素
        del result[seen[item]]
    # 更新元素的最新索引（当前deque的长度，因为即将append到末尾）
    seen[item] = len(result)
    result.append(item)

final = list(result)
print(final)  # 输出: ['b', 'a', 'c']

方案对比 #

• 原方案：两次反转（O(n)时间）+ dict.fromkeys（O(n)时间），但反转需要复制整个列表，大数据量下内存占用高
• 基础deque方案：遍历一次列表，整体效率接近O(n)（重复率低时），无需复制整个列表，内存开销更小
• 优化版deque方案：全程O(n)时间复杂度，所有操作均为常数级，是大规模列表场景下的最优选择之一

内容的提问来源于stack exchange，提问作者ans_ak