0

刚刚进行了一次面试测试，我必须在列表中找到第一个唯一（非重复）元素并将其返回。如果没有找到唯一元素，则返回 -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
4

5 回答 5

7

这可能是最有效的方法。它是 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
于 2013-09-12T15:16:52.517 回答
7

使用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)
于 2013-09-12T14:47:50.920 回答
3

我会把我的版本扔进戒指：

def solution(lst):
    seen = set()
    for i in lst:
        if i in seen:
            continue
        if lst.count(i) == 1:
            return i
        else:
            seen.add(i)
    return -1

计时器：

import timeit
from collections import OrderedDict
test = [1,2,1,3,2,5]

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

def inbar(lst):
    seen = set()
    for i in lst:
        if i in seen:
            continue
        if lst.count(i) == 1:
            return i
        else:
            seen.add(i)
    return -1

>>> print timeit.Timer('inbar(test)', 'from __main__ import *').repeat()
[1.4576762138175334, 1.4347494767197622, 1.4615902215846446]

>>> print timeit.Timer('falsetru(test)', 'from __main__ import *').repeat()
[26.38230001155711, 27.358966390824754, 29.19406918489357]

我对这些结果感到惊讶。

于 2013-09-12T14:50:16.550 回答
2

在代码的最后一部分：

for i in lst:
    if lst.count(i) == 1:
        return i

您在 for 循环的每次迭代中都遍历列表。这导致 O(n^2)，这相当慢且不是最优的。

我建议用这段代码替换这部分：

lst.sort()

for i in range(len(lst)):
    if i == 0:
        if lst[i] != lst[i+1]: # if not same as next element
            return lst[i] # okay, it's unique
    if i == len(lst) - 1: # it's the last element
        if lst[i-1] != lst[i]: # let's check if the previous element is the same
            return lst[i] # okay, it's unique
    if lst[i-1] != lst[i] and lst[i] != lst[i+1]: # let's check if the previous element and next element are both not equal to the current element
        return lst[i] # okay, it's unique

排序算法在 O(n log n) 中完成并且遍历列表是 O(n)，所以它是 O(n log n)。

编辑：发现 Shashank Gupta 在我之前发布过，所以这里有另一个版本需要考虑。

于 2013-09-12T15:22:31.437 回答
0

对你的采访感到抱歉。下一次，用numpy一个衬里解决方案给他们留下深刻印象：

>>> a=array([1,2,1,3,2,5])
>>> a[sum(a==a.T[...,newaxis], axis=1)==1][0]
3

好的，不完全是单线。您需要使用try except来捕捉每个元素都不是唯一的情况。

于 2013-09-12T16:13:37.780 回答