어떻게 내가 O에서의 ArrayList에서 중복 요소를 제거 할 (logn) 시간

Question

나는 ArrayList의 요소로 문자열을 가지고 내가 HashSet를 사용하여 시도 자바

를 사용하여, O (logn) 시간에 그들을 제거 할 것 복사하고 지우고 다시 다른 arraylist로 복사하려면,하지만 그것은 O (n) 시간이라고 생각합니다.

Answer 1

배열을 정렬 한 경우에도 가능하지 않다고 생각합니다. O(n)이 걸릴 것입니다. 적어도 각 요소를 검사하는 것을 피할 수는 없으므로 O(n) 미만의 복잡성을 갖는 것은 불가능합니다.

Answer 2

배열의 문자열이 정렬 된 순서 인 경우 이진 검색을 사용하여 O (log n) 시간에 액세스 할 수 있습니다. 그러나 정렬되지 않은 경우 배열의 각 요소를 검사하여 O (n)의 하한값을 지정해야합니다.

EDIT : 이미 생성 된 ArrayList에서 중복을 제거하려는 경우 O (n) 시간이 걸릴 각 요소를 확인해야합니다. 추가 할 때 희생 할 의사가있는 경우 배열에 정렬 된 순서로 추가 할 수 있습니다. 그러면 요소가 이미 있으면 추가하지 않기 때문에 중복을 제거 할 필요가 없습니다. 그러나 추가는 일정 시간이 아닌 선형 시간으로 실행됩니다.