다른 두 목록에있는 모든 요소는 어떻게 찾습니까?

Question

2 개의 튜플을 인수로 취하고 두 튜플에있는 요소를 포함하는 정렬 된 튜플을 반환하는 함수 commonElements (a1, a2)를 작성합니다.

내 작업은 다음과 같습니다

>>> commonElements((1, 2, 3), (2, 5, 1)) 
    (1, 2) 
    >>> commonElements((1, 2, 3, 'p', 'n'), (2, 5 ,1, 'p')) 
    (1, 2, 'p') 
    >>> commonElements((1, 3, 'p', 'n'), ('a', 2 , 5, 1, 'p')) 
    (1, 'p') 

내가 이런 식으로 작업을 수행하려고 노력했다.

def commonElements(a1, a2): 
    return tuple(set(a1).intersection(set(a2))) 

누구나 내 실수가 요구 사항을 알고 있습니까?
전달할 수 없습니다.

Answer 1

세트가 주문되어 있지 않습니다. 따라서 결과의 순서는 임의적 일 수 있습니다. 내가 그런 일 가지고 올 것이다 :

def commonElements(a1, a2): 
    L = [] 
    for el in a1: 
     if el in a2: 
      L.append(el) 
    return tuple(L) 

하십시오, 참고, 튜플 a1 같이 주문한 출력 요소를 얻을 것입니다 문제를 해결하는이 방법이. 따라서 주석에 언급 된 바와 같이,이를 호출하는 올바른 방법은 '정렬'이 아니라 '정렬'입니다. 또한 O(n*m)의 복잡도를 가지고 있습니다. 여기서 n 및 m은 각각 a1 및 a2의 길이입니다.

O(n*log(m))이 경우 bisect 모듈이 두 번째 튜플 a2 (진행하기 전에 정렬되어야 함)의 요소에 액세스하는 데 사용되는 경우 얻을 수 있습니다.

평균에

def commonElements(a1, a2): 
    return tuple(sorted(set(a1).intersection(set(a2)))) 

그것이 O(min(m+n)*log(min(n+m)))의 복잡성 (때문에 정렬)이 있고, 최악의 O(n*m) : 일반적인 방법으로 정렬하는 것이 필요한 경우

, 당신의 코드와 스틱 것, 조금 변경 케이스가 intersection입니다.

코드가 필요한 경우

여기 (연구의 목적을 위해, 예를 들어) set를 사용하지 않고 구현 된 코드합니다 :

def commonElements(a1, a2): 
    L = [] 
    for el in a1: 
     if el in a2: 
      L.append(el) 
    L.sort() 
    return tuple(L) 

복잡성이 O(n*m)입니다.이 방법을 보일 것이다 bisect 코드를 사용하여

:

from bisect import bisect_left 
def commonElements(a1, a2): 
    L = [] 
    a2.sort() #sort a2 to be able to use binary search in the internal loop thus changing the complexity from O(n^2) to O(n*log(n)) (assuming n and m are rather equal). 
    a2_len = len(a2) 
    for el in a1: 
     i = bisect_left(a2, el) 
     if i != a2_len and a2[i] == el: 
      L.append(x) 
    # L.sort() #uncomment this line if the list in sorted order is needed (not just ordered as the first lits; it's possible to sort a1 in the very beginning of the function, but that would be slower on the average since L is smaller on the average than a1 or a2 (since L is their intersection). 
    return tuple(L) 

복잡성 O(n*log(m))입니다.

Answer 2

정렬 요구 사항을 잊었습니까?

편집

은 분명히, 세트는 오름차순으로 요소를 정렬하지만, 이것은 아마도 구현 세부입니다. 이 함수를 테스트로 작성하라는 요청을 받았다면 설정을 위임하는 대신 모든 것을 구현해야 할 수도 있습니다. 완성도를 들어

편집 2

, 요구 사항을 충족해야합니다 구현 :

def commonElements(a1, a2): 
    common = [] 
    for x in a1: 
     if x in a2: 
      common.append(x) 
    common.sort() 
    return tuple(common) 

Answer 3

def commonElements(a1, a2): 
    return tuple(sorted(set(a1).intersection(set(a2)))) 

Answer 4

프로그램이 나를 위해 작동하는 것 같습니다. python-2.7.1 +.

그러나, 그 세트는 정의에 따라 "순서가 없음"입니다. 따라서 "교차점"에서 생성 된 집합도 순서가 지정되지 않습니다.

요소를 정렬 한 튜플에 이것을 얻으려면 추가 코드가 필요합니다.

def commonElements(a1, a2): 
    intersection = list(set(a1).intersection(set(a2))) 
    intersection.sort() 
    return tuple(intersection) 

http://docs.python.org/library/sets.html ,

Answer 5

또 다른 간단한 예제 솔루션의 라인을 따라

아마 뭔가. 이것이 내가 그것을 쓰는 방법이다. 최단 해결책?

def commonElements(a1, a2): 
     return tuple(sorted([x for x in a1 if x in a2]))