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

使用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

UPDATE：使用する代替ソリューション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 に答える
7

これはおそらく最も効率的な方法です。リストを 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
于 2013-09-12T15:16:52.517 に答える
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

OK、正確にはワンライナーではありません。try exceptすべての要素が一意ではない状況をキャッチするために使用する必要があります。

于 2013-09-12T16:13:37.780 に答える