python - 2 つのリストの最初の共通要素

Question

x = [8,2,3,4,5]
y = [6,3,7,2,1]

簡潔かつエレガントな方法で、2 つのリスト (この場合は「2」) の最初の共通要素を見つける方法は? どのリストも空にすることも、共通の要素が存在しないこともできます。この場合は、None で問題ありません。

これは、python を初めて使用する人に見せるために必要なので、単純であるほど良いです。

UPD: 順序は私の目的にとって重要ではありませんが、y でも発生する x の最初の要素を探していると仮定しましょう。

Answer 1

forでループを使用するinとO(N^2)複雑になりますが、yここで並べ替えて二分探索を使用すると、時間の複雑さが に改善されO(NlogN)ます。

def binary_search(lis,num):
    low=0
    high=len(lis)-1
    ret=-1  #return -1 if item is not found
    while low<=high:
        mid=(low+high)//2
        if num<lis[mid]:
            high=mid-1
        elif num>lis[mid]:
            low=mid+1
        else:
            ret=mid
            break

    return ret

x = [8,2,3,4,5]
y = [6,3,7,2,1]
y.sort()

for z in x:
    ind=binary_search(y,z)
    if ind!=-1
        print z
        break

出力： 2

モジュールを使用しbisectて上記と同じことを実行します。

import bisect

x = [8,2,3,4,5]
y = [6,3,7,2,1]
y.sort()

for z in x:
    ind=bisect.bisect(y,z)-1  #or use `ind=min(bisect.bisect_left(y, z), len(y) - 1)`
    if ind!=-1 and y[ind] ==z:
        print z      #prints 2
        break     

Answer 2

あなたはプログラミングだけでなく、この人に Python を教えたいと思っていると思います。zipしたがって、醜いループ変数の代わりに使用することを躊躇しません。これは Python の非常に便利な部分であり、説明するのは難しくありません。

def first_common(x, y):
    common = set(x) & set(y)
    for current_x, current_y in zip(x, y):
        if current_x in common:
            return current_x
        elif current_y in common:
            return current_y

print first_common([8,2,3,4,5], [6,3,7,2,1])

本当に を使用したくない場合はzip、次の方法で使用できます:

def first_common2(x, y):
    common = set(x) & set(y)
    for i in xrange(min(len(x), len(y))):
        if x[i] in common:
            return x[i]
        elif y[i] in common:
            return y[i]

そして、興味のある人のために、これが任意の数のシーケンスに拡張される方法です:

def first_common3(*seqs):
    common = set.intersection(*[set(seq) for seq in seqs])
    for current_elements in zip(*seqs):
        for element in current_elements:
            if element in common:
                return element

最後に、他のいくつかのソリューションとは対照的に、これは最初の共通要素が 2 番目のリストの最初に表示される場合にも機能することに注意してください。

あなたの更新に気付きました。これにより、さらに簡単な解決策が得られます。

def first_common4(x, y):
    ys = set(y) # We don't want this to be recreated for each element in x
    for element in x:
        if element in ys:
            return element

上記は、おそらくジェネレーター式よりも読みやすいです。

残念ながら、組み込みの順序付きセットはありません。それはよりエレガントなソリューションを作ったでしょう。

Answer 3

これはセットを使用します。最初の共通要素を返すか、共通要素がない場合は None を返します。

def findcommon(x,y):
    common = None
    for i in range(0,max(len(x),len(y))):
        common = set(x[0:i]).intersection(set(y[0:i]))
        if common: break
    return list(common)[0] if common else None

Answer 4

def first_common_element(x,y):
    common = set(x).intersection(set(y))
    if common:
        return x[min([x.index(i)for i in common])]

Answer 5

セットを使用 - これは、任意の数のリストに対する一般的な解決策です。

def first_common(*lsts):
    common = reduce(lambda c, l: c & set(l), lsts[1:], set(lsts[0]))
    if not common:
        return None
    firsts = [min(lst.index(el) for el in common) for lst in lsts]
    index_in_list = min(firsts)
    trgt_lst_index = firsts.index(index_in_list)
    return lsts[trgt_lst_index][index_in_list]

後付け - 効果的なソリューションではありません。これにより、冗長なオーバーヘッドが削減されます

def first_common(*lsts):
    common = reduce(lambda c, l: c & set(l), lsts[1:], set(lsts[0]))
    if not common:
        return None
    for lsts_slice in itertools.izip_longest(*lsts):
        slice_intersection = common.intersection(lsts_slice)
        if slice_intersection:
            return slice_intersection.pop()