Python:列表中的第一个唯一编号

Question

刚进行了一次面试测试,我必须在列表中找到第一个唯一(非重复)元素并将其返回.如果未找到唯一元素,则返回-1.我被告知我的解决方案不是最佳的.有人可以提出更好的方法吗？

这是我的代码:

def solution(lst):
    if len(lst) == 1:
        return lst[0]
    elif lst == []:
        return -1
    for i in lst:
        if lst.count(i) == 1:
            return i
    return -1

Answer 1

使用collection.OrderedDict:

def solution(it):
    d = OrderedDict()
    for x in it:
        d[x] = d.get(x, 0) + 1
    return next((x for x in d if d[x] == 1), -1)

例:

>>> solution([1,2,1,3,2,5])
3
>>> solution([1,2,1,3,3,2,5])
5
>>> solution([1,2,1,3,3,2,5,5])
-1

更新:使用的替代解决方案collections.Counter

def solution(seq):
    d = Counter(seq)
    return next((x for x in seq if d[x] == 1), -1)

Answer 2

这可能是最有效的方法。它是 O(n)，因为它只是列表的两次遍历。

仅供参考，您的解决方案显然是 O(n^2)，这可能就是您的面试官不喜欢它的原因。

# Fast O(n) solution using a dictionary
def solution(lst):
    counts = {}

    for item in lst:
        if item in counts:
            counts[item] += 1
        else:
            counts[item] = 1

    for item in lst:
        if counts[item] == 1:
            return item

    return -1

print(solution([1,2,1,3,2,5])) # prints 3
print(solution([1,2,1,3,3,2,5])) # prints 5
print(solution([1,2,1,3,3,2,5,5])) # prints -1
print(solution([7])) # prints 7