n 개의 목록 교차점

Question

나는 C++에서 N 개의 목록 교차를 찾는 방법을 찾아 내려고 노력해 왔습니다.

나를 클릭하는 방법은 정렬, 병합 및 반복입니다.

다른 방법이 있습니까?

의견을 보내주십시오.

Answer 1

정렬되지 않은 목록을 사용하는 솔루션은 복잡합니다. 아마, 당신은 처음에는 비어있는 '대답'목록을 가지고있을 것입니다. 그런 다음 두 개의 목록을 확인하고 한 단계 씩 실행합니다. 각 요소에 대해 다른 목록을 스캔하여 목록에 있는지 확인합니다. 일치하는 항목이 있으면 대답에 요소를 저장합니다. 그런 다음 비어있는 새 대답 목록을 만들고 원래 목록의 다른 단계를 거치고 일치하는 요소에 대한 이전 대답 목록을 검색 한 다음 새 대답 목록에 추가합니다. 광고 구역 반복.

이것은 특별히 효율적이지 않습니다.

'정렬, 병합 및 반복'솔루션의 경우 목록 쌍을 사용하여 동시에 N 개의 정렬 된 목록을 반복하는 것만 큼 효과적이지 않으며 모든 목록에있는 요소를 대답.

Answer 2

정렬은 반복적 std::set_intersection을 이용하여 교차를 계산 (그것이 std::list을인지하거나, std::list::sort 사용) std::sort를 사용하여 각리스트 (결과 및에이어서, 그 결과 세 번째리스트에 첫 번째 두 목록에 적용 네 번째 목록 등).