삽입 정렬을 사용하여 중복 제거 Java

Question

다음 코드에서 절반의 문제가 발생했습니다. 이는 Comparable 인터페이스와 함께 사용되는 삽입 정렬 방법입니다. 이 특정한 경우에는 요소를 내림차순으로 정렬해야하는데, 이는 잘됩니다. 그러나 동일한 메서드 내에서 중복을 제거하려고하지만 작동하지 않습니다. 동일한 방법으로 실제로 그렇게 할 수 있는지 궁금합니다. 나는 다음 질문에 대답을 보았다 Removing Duplicates Inside Insertion Sort 그러나 나는 그것을 여기에 적용하는 방법을 잘 모르겠다. 반드시 솔루션을 찾고있는 것이 아니라 내가 올바른 방향으로 나를 안내 할 수 있다면 더 멀리 나아갈 수 있습니다. 미리 감사드립니다.

public void InsertionSortDecrease(){ 
    for(int i=1;i<size();i++){ 
     T keyelement = get(i); 
     int pos=i; 
     while(pos > 0 && 
(((Comparable)keyelement).compareTo((Comparable)get(pos-1)) > 0)){ 
      set(pos,get(pos-1)); 
      pos--; 
     } 
     set(pos,keyelement); 
     if(((Comparable)get(pos)).compareTo((Comparable)get(pos+1)) 
== 0){ 
      remove(pos); 
     } 
    } 
} 

Answer 1

정렬하는 동안 요소를 제거하려고합니다. 이 같은 것을 위해 Iterator는 동시 수정 오류가 발생하는 것을 피하는 것이 훨씬 낫습니다.

Answer 2

나는 개인적으로 당신이 원하는 것을 수행하는 TreeSet을 사용할 것입니다.

항목이 아직 정렬되어있는 세트에없는 경우에만 add 항목 만 표시 할 수 있습니다. 당신이 삽입을 찾기로 바로에 셔플해야하므로 최종 결과의 왼쪽에 더 이상 공간이 없기 때문에

Answer 3

버그, 당신은 최대 계산되지만, 당신이 아래로을 를 계산해야한다입니다 포인트.

그러면 첫 번째 루프의 종료 조건으로 인해 다음 위치보다 작음을 알 수 있으므로 현재 위치와 이전 위치 (있는 경우) 위치를 비교해야합니다. 하지만 속임수라면 모두 뒤섞어 써야합니다.

더 나은 방법은 삽입 지점을 찾는 것입니다. 그런 다음 삽입 방법이 다른 경우에는 아무 것도 수행하지 않고 삽입합니다. 이런 식으로 코드를 리팩터링하면 정렬 된 데이터로 작동한다는 것을 알고 있으므로 바이너리 검색을 수행하여 O (n)에서 O (log n)까지 삽입 점 찾기를 향상시킬 수 있습니다.