벡터에서 첫 번째 중복 항목을 찾는 방법 - C++?

Question

다른 값을 가진 벡터를 가지고 있는데 그 중 일부는 일 수 있습니다.이 두 번 나타납니다. (두 번만)
첫 번째 중복 항목은 어떻게 찾을 수 있습니까?

좋아요 : [a] [b] [b] [a]
그런 다음 'b'가 필요합니다. 당신이 인접한 중복을 찾고 있다면 (초보자 질문에 대한 죄송합니다.)

Answer 1

, 당신은 단순히 std::adjacent_find를 사용할 수 있습니다.

중복이 반드시 인접하지 않은 경우 먼저 std::sort 벡터를 입력 한 다음 결과에 std::adjacent_find을 사용할 수 있습니다.는

또는 당신이 std::set에 각 요소를 밀어 수 있습니다 (아래 @의 AIX의 설명을 참조하십시오), 당신이 그것을하고있는 것처럼 충돌을 찾습니다.

Answer 2

이 질문에 대한 답변이 많이 있습니다. 이 인 것으로 확인하려면 사용 시나리오의 컨텍스트를 알아야합니다. 예를 들어, ok 처음에는 중복이 있습니까? 중복 검색의 결과로 무엇을 할 것입니까? 항상 벡터에 평행 구조를 사용할 수 있습니까? 그리고 더 ...

그래서 많은 방법 중 하나는 항목을 반복하고 insert을 std::set<>으로 바꾸는 것입니다. 반환 된 std::pair<>의 second 매개 변수를 살펴보고 그 값이 세트에 존재하는지 여부를 확인한 다음 첫 번째 복제본을 가져오고 set- 추가로 빠져 나올 수 있습니다.

Answer 3

추가 저장 장치를 사용하지 않으려면 대략 두 가지 해결책이 있습니다. 첫 번째는 무차별 대항력 (brute-force)입니다. 모든 요소 i에 대해 요소 0..i-1과 같은지 확인하십시오. 이것은 O(N*N)입니다 (최악의 경우 : 마지막 두 요소가 첫 번째 중복입니다).

둘째 해결 방법은 범위를 0..i로 유지하여 검색 속도를 높이는 것입니다. 정렬. 정렬하는 동안 중복 된 것을 쉽게 찾을 수 있습니다. 버블 정렬은 이전 반복에서 0..i-1 범위가 이미 정렬 되었기 때문에 효율적입니다. 여전히 O(N*N) 최악의 경우이지만 범위가 이전에 정렬 된 경우 O(N)입니다.