중복 된 요소가 두 개 이상있는 경우 배열에서 중복 찾기

중복 된 요소가 두 개 이상인 경우 어떻게 배열에서 중복 된 항목을 찾을 수 있습니까? 어레이는 하나의 중복 원소중복 된 요소가 두 개 이상있는 경우 배열에서 중복 찾기

는

(예 : 1, 2, 3, 4, 4, 4, 5, 6, 7)을 매우 간단하다

int duplicate(int* a, int s) 
{ 
    int x = a[0]; 
    for(int i = 1; i < s; ++i) 
    { 
     x = x^a[i]; 
    } 
    for(int i = 0; i < a[s]; ++i) 
    { 
     x = x^i; 
    } 
    return x; 
}

그러나 만약 입력 배열에 복제 된 요소가 두 개 이상 포함되어 있으면 (예 : 1,2,2,3,4,4,4,5,6,7) 위의 코드는 작동하지 않습니다. O (n) 시간에 어떻게이 문제를 풀 수 있습니까?

출처

2013-12-09 Anonymous

배열이 정렬되어 있습니까? –

그래,하지만 흥미로운 경우와 배열이 정렬되지 않은 경우. –

여기에 뭐라구? 이 XOR 연산은 모두 무엇입니까? 그리고 왜 이상한 구문 ('a (s-1)'대신에'(a + s-1)')이 필요한가? –

공백이 없거나 최대 수가 매우 적은 경우 비트 배열의 종류를 사용하고 숫자 위치에 비트를 설정하여 이미 생성 된 모든 숫자를 표시 할 수 있습니다.

사소한 (신원) 해시 함수를 사용하는 일종의 HashSet입니다. 테스트 및 설정 비용은 O(1)입니다.

출처

2013-12-09 08:56:39 MrSmith42

집합을 사용하면 가능한 일반적인 솔루션 중 하나입니다. C++에서, 예 : unordered_set로서

template <typename T> 
void filter_duplicates(T* arr, int length) { 
    std::unordered_set<T> set; 
    for (int i = 0; i < length; ++i) { 
     if (set.count(arr[i]) > 0) { 
      // then it's a duplicate 
     } 
     set.insert(arr[i]); 
    } 
    // the set contains all the items, unduplicated 
}

해시 테이블, 삽입 및 룩업으로서 구현된다 일정한 상각 복잡하다. 집합에는 고유 키만 포함될 수 있으므로 항목을 효과적으로 중복 제거합니다. 마침내 세트를 배열로 다시 변환 할 수 있습니다. 또한지도를 사용하여 어커런스를 계산할 수도 있습니다.

배열 요소가 정수이고 가능한 최대 값을 알고 매우 낮 으면 집합은 다음 중 하나의 부울 값 또는 정수 2의 간단한 배열로 대체 될 수 있습니다. 발생.

출처

2013-12-09 08:53:58 Jean

중복 된 요소가 두 개 이상있는 경우 배열에서 중복 찾기

답변

관련 문제