Python面试题系列之08: 设计删除列表中的重复元素？

Question

请写出一段 Python 代码，实现删除一个 list 里面的重复元素?

list_ori = ['p', 'y', 't', 'h', 'o', 'n', 'i', 's', 't', 'a']

知识点详解

去除重复元素，最常用的就是采用内置的set方法

list_ori = ['p', 'y', 't', 'h', 'o', 'n', 'i', 's', 't', 'a']
l0 = list(set(list_ori))
print(l0)
>>> ['n', 'a', 's', 'y', 'i', 'h', 'p', 'o', 't']

方法一
上面例子中，我们使用set方法虽然实现了去重，但打乱了元素的排列顺序。

若想要保持它们原本的排序，我们可以利用上一篇提到的list操作中的sort方法来实现，只需把原列表的索引设置为key。

list_ori = ['p', 'y', 't', 'h', 'o', 'n', 'i', 's', 't', 'a']
l1 = list(set(list_ori))
l1.sort(key=list_ori.index)
print(l1)
>>> ['p', 'y', 't', 'h', 'o', 'n', 'i', 's', 'a']

方法二

看过上篇文章的同学，肯定会想到既然sort方法可以实现这个需求，那么用sorted函数自然也是可以的。

list_ori = ['p', 'y', 't', 'h', 'o', 'n', 'i', 's', 't', 'a']
l2 = sorted(set(list_ori), key=list_ori.index)
print(l2)
>>> ['p', 'y', 't', 'h', 'o', 'n', 'i', 's', 'a']

方法三

这里我们不再借助内置的set、sort/sorted方法，再换个思路，用for循环来实现这个需求：用for循环遍历列表，将取出元素存入新列表中，在存入时只需判断元素是否已存在即可实现去重的效果。

list_ori = ['p', 'y', 't', 'h', 'o', 'n', 'i', 's', 't', 'a']
l3 = []
for i in list_ori:
    if i not in l3:
        l3.append(i)
print(l3)
>>> ['p', 'y', 't', 'h', 'o', 'n', 'i', 's', 'a']

方法四

再换一个思路：引入临时变量。我们声明一个临时变量tmp，设定初始值tmp=data[0], index=0。对原列表排序后，执行遍历操作，若data[i]与tmp相同则跳过；当两者值不同时：将tmp赋值给data[index]，然后将data[i]赋值给tmp、同时index加1。

def l4(data=None):
    data = sorted(data, key=data.index)
    tmp = data[0]
    index = 0
    for i, v in enumerate(data):
        if tmp == v:
            continue
        else:
            data[index] = tmp
            tmp = v
            index += 1
    data[index] = tmp # 上面for循环中最后一次的tmp值没有赋给data，这里要补上
    return data[:index+1] # 因为index从0开始，所以此处需加1

接下来我们调用函数，看下是否和前面三种方法得到的结果一致

print(l4(data=list_ori))
>>> ['p', 'y', 't', 'h', 'o', 'n', 'i', 's', 'a']

这种方法的空间复杂度为O(1)，时间复杂度为O(N)。与方法三相比，这里仅遍历了一次，算法上已是最优解了。

Answer

此问题的解决方案，详见上文所述。

后记

俗话说“条条大路通罗马”，用python代码实现这个列表去重的需求，远不止上述这些方法。欢迎大家在评论区留言给出自己的解决方案。好了，以上就是本篇全部内容。

备注：本篇首发于知识星球「人人都是Pythonista」。