Python算法题----列表去重

py3study

发布于 2020-01-07 16:41:19

1.9K0

发布于 2020-01-07 16:41:19

文章被收录于专栏：python3

有这样一个列表[1, 1, 1, 2, 3, 3, 2, 4, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10, 10], 写一个函数，将其重复元素去除。

这道题，方法很多的有没有。下面就演示一下茴香豆的四种写法。

解法一：

Python的内置特性

利用python set数据结构的不重复行，转换为set，然后再转为list，一行代码搞定

def uniqList01(data=None):
    return list(set(data))

解法二：

遍历搜索去重添加

创建一个新列表，遍历旧的列表，先把第一个塞进新列表中，然后判断每一个元素在新列表中是否存在，不存在就塞进去。

def uniqList02(data=None):
    newdata = [data[0]]
    for i in data[1:]:
        if i not in newdata:
            newdata.append(i)
    return newdata

解法三：

双指针比较跳过重复

i,j两个指针分别指向第i个和第i+1个元素，比较，相等j后移，直到不等将第i个元素加到新列表。j赋给i，开始下一次循环即可。

该方法时间复杂度由于解法2，毕竟解法二中的in判断也是一种遍历。

def uniqList03(data=None):
    data = sorted(data)
    newdata = []
    stop = len(data) - 1
    i = 0
    while i <= stop:
        j = i + 1
        if i == stop:
            newdata.append(data[i])
            i += 1
        else:
            if data[i] == data[j]:
                while j <= stop and data[i] == data[j]:
                    j += 1
            newdata.append(data[i])
            i = j
    return newdata

解法四：

临时变量大法

声明临时变量tmp=data[0], index=0。变量data，如果相等则continue，不相等。将data[index]赋值为tmp，tmp=data[i], index++即可。

该解法空间复杂度为O(1), 时间复杂度为O(N)，应该算是最优解了。

def uniqList04(data=None):
    data = sorted(data)
    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  # 在foreach循环中，最后一次的tmp值没有赋给data
    return data[:index+1]  # 因为index从0开始，所以此处加1

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/09/11 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法