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

发布时间：2019-09-11 07:42:16编辑：auto阅读（1583）

    有这样一个列表[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


关键字：

上一篇： Python自动更新脚本

下一篇： python requests post