0

先週のインタビューでこれを尋ねられたのですが、答えがありませんでした(とにかく正解です)。たとえば、[1,3,5,7,9,10] の要素を持つリスト A があり、[3,4,5,6,7] の要素を持つリスト B があるとします。リスト B のどの要素がリスト A に含まれているかを知りたいとします。私の答えは次のとおりです。

for item in listA:
    for item1 in listB:
        if item1 == item:
            put item1 in some third list

しかし、listA が 100 万個の要素で、listB が 10 万個の要素であるとすると、この解決策はただのごみです。

両方のリストを反復せずにこのようなことを達成する最善の方法は何ですか?

4

5 に答える 5

6

set(listA) & set(listB)最も簡単です。

于 2012-08-21T04:29:20.723 に答える
2

それらを両方ともセットに変換し、交差させることをお勧めします。

setA = set(listA)
setB = set(listB)
setA.intersection(setB)

編集:これにより、両方のリストにあった重複要素がすべて削除されることに注意してください。したがって、もし私たちが持っていたらlistA = [1,1,2,2,3]listB = [1,1,2,3]交差点はだけになりますset([1,2,3])。また、最悪の場合の見積もりでは、これはリスト内包表記と同じくらい遅くなりO(n * m)ます。ここで、nとmはリストのそれぞれの長さです。ただし、平均的なケースの方がはるかに優れていO(n) + O(m) + O(min(m,n)) == O(max(m,n))ます。

于 2012-08-21T04:30:19.637 に答える
1

リスト内包表記を使用し、in演算子を使用してメンバーシップをテストします。

[i for i in lista if i in listb]

降伏します:

[3, 5, 7]

あるいは、集合演算を使用して、両方のリスト(集合に変換されたもの)の共通部分がどうなるかを確認することもできます。

于 2012-08-21T04:30:05.810 に答える
1

まあ、ミックスにフィルターを入れてもいいです

filter(lambda x: x in listb,lista)
于 2012-08-21T04:34:32.190 に答える
0

セットを使用できます(推奨):

listC = list(set(listA) & set(listB))

またはリスト内包表記:

listC = [i for i in listA if i in listB]
于 2012-08-21T04:29:32.023 に答える