python - 为什么我的第二种方法比第一种方法慢？

Question

我在做leetcode题没有。 387. 字符串中的第一个唯一字符。给定一个字符串，找到其中的第一个非重复字符并返回它的索引。如果不存在，则返回-1。

例子:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

我写了2个算法:

方法一

def firstUniqChar(s):
    d = {}
    L = len(s)
    for i in range(L):
        if s[i] not in d:
            d[s[i]] = [i]
        else:
            d[s[i]].append(i)
    M = L
    for k in d:
        if len(d[k])==1:
            if d[k][0]<M:
                M = d[k][0]
    if M<L:
        return M
    else:
        return -1

这非常直观，即首先通过遍历 s 中的所有字符创建一个计数字典(这也可以使用 collections.Counter 中的一行来完成) )，然后进行第二个循环，只检查那些值为长度为 1 的列表的键。我认为我做了 2 个循环，它必须有一些冗余计算。所以我写了第二个算法，我认为它比第一个算法好，但是在 leetcode 平台上，第二个算法比第一个算法运行得慢得多，我不明白为什么。

方法二

def firstUniqChar(s):
    d = {}
    L = len(s)
    A = []
    for i in range(L):
        if s[i] not in d:
            d[s[i]] = i
            A.append(i)
        else:
            try:
                A.remove(d[s[i]])
            except:
                pass

    if len(A)==0:
       return -1
    else:
       return A[0]

第二个只为 s 中的所有字符循环一次

Answer 1

您的第一个解决方案是O(n)，但您的第二个解决方案是O(n^2)，因为方法A.remove正在遍历 A 的元素。