가능한 중복을 중복을 제거하는 방법 :
Array remove duplicate elements배열에서
이 숙제 질문입니다. 가장 좋은 방법은 수정 된 merge sort입니다. 수정 된 merge은 중복 입력 요소를 두 입력 배열에서 결과 배열로 복사하지 않습니다. 복잡성은 O (N * logN)입니다 (정확히 merge sort과 동일). 그것은 의미가 있습니까? 더 나은 해결책이 있습니까?
정렬 할 필요가없는 경우 a를 사용하여 O (N) 시간에 수행 할 수있는 중복 만 제거합니다. HashSet (또는 해당 언어).
감사합니다. 나는 정렬 할 필요가 없습니다. 배열 요소를 세트로 복사하고 세트를 배열로 복사 할 수 있습니다. BTW, 하나 TreeSet 배열 정렬 할 수 있습니다. – Michael
조심하십시오. TreeSet을 사용하면 O (n * log (N))로 되돌아갑니다. – threenplusone
그러나 정렬을 통해 n 방향 정렬 또는 유사하게 사용할 수 있습니다. 데이터 세트가 메모리에 잘 맞지 않으면 매우 편리합니다. 그러나 그것은 이미 "다른 문제들"의 영역에 있습니다 : p –
좋은 소리입니다. 또는 어떤 종류의 정렬을 수행 한 다음 복잡성이있는 중복을 제거 할 수 있습니다. O (N) ...
먼저 배열을 정렬해야합니다. 정렬 된 배열이므로 모든 중복은 서로 옆에 있습니다. 그러니 처음부터 시작하여 각 요소를 오른쪽에있는 이웃 요소와 비교하십시오. 중복이 없으면 n-2 비교를 수행하고 완료됩니다.
중복 된 것을 발견하면 구멍이 생길 것입니다. 링크 목록이 아니기 때문에 모든 요소를 아래로 이동해야합니다. (허용되는 경우 새 배열을 만들 수 있습니다.) 그러나 모든 것을 아래로 움직이기를 원할뿐만 아니라 단순히 구멍이있는 포인터 나 카운터로 표시하고 다음 비교로 넘어갈 수 있습니다. 다음 비 복제물을 얻으면 해당 요소를 구멍으로 이동 (복사)하고 홀 카운터를 1 씩 증가시킵니다.
가능한 중복 : http://stackoverflow.com/questions/3350641/array-remove-duplicate- 요소, http://stackoverflow.com/questions/9673/remove-duplicates-from-array, http://stackoverflow.com/questions/3432760/remove-duplicate-elements-in-an-array-in-on- in-cc, http://stackoverflow.com/questions/357421/what-is-the-best-way-to-remove-duplicates-in-an-array-in-java, http://stackoverflow.com/ 질문/4395668/remove-duplicates-from-without-using-hash-table, http://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an- 배열 –