세트를 사용하지 않고 배열에서 중복 항목을 효율적으로 제거하려면 어떻게 해야 합니까?

Set을 사용하지 않고 배열에서 중복 항목을 효율적으로 제거

배열에서 중복 요소를 제거하기 위한 맞춤형 솔루션을 만들기 위해 노력하셨습니다. 그러나 성능 병목 현상이 나타났습니다. 이 구현을 최적화하기 위해 우리는 접근 방식의 단점을 분석하고 대체 전략을 제안할 것입니다.

알고리즘 분석

알고리즘은 각 항목을 비교하여 중복 항목을 검색하려고 시도합니다. 모든 후속 요소와 요소. 이러한 철저한 비교로 인해 O(n^2) 시간 복잡도가 발생합니다. 대규모 어레이의 경우 이 전략은 매우 비효율적일 수 있습니다.

최적화된 접근 방식

성능을 크게 향상하려면 다음 최적화를 고려할 수 있습니다.

1. 해시 맵 활용: 작업 중에 발견한 고유 요소를 저장하기 위해 해시 맵을 구현합니다. 반복. 각 요소가 배열에 추가되면 해당 요소가 이미 해시 맵에 키로 존재하는지 확인하세요. 그렇지 않은 경우 추가하십시오. 이 접근 방식을 사용하면 효율적인 상수 시간 조회 작업이 가능해 시간 복잡도가 O(n)으로 줄어듭니다.
2. 필터링 전 정렬: 배열을 오름차순으로 정렬합니다. 이제 중복 요소는 서로 인접하게 됩니다. 정렬된 배열을 반복하고 인접한 중복 항목을 제거하여 선형 시간 O(n) 알고리즘을 만듭니다.

대체 솔루션

앞서 언급한 최적화를 통해 다음을 수행할 수 있습니다. 알고리즘 성능을 향상시키려면 다른 확립된 방법을 고려할 수도 있습니다. 기술:

• 세트 컬렉션: 세트 사용을 피해야 하므로 이 옵션은 자세히 다루지 않겠습니다.
• 정렬된 컬렉션 사용 : 필터링 전 정렬과 유사하게 TreeSet 또는 NavigableSet과 같은 정렬된 컬렉션을 활용하세요. 자동으로 정렬된 순서를 유지하고 효율적인 요소 검색을 허용하므로 O(n log n) 복잡성이 발생합니다.

구현

최적화된 접근 방식을 기반으로, 해시 맵을 활용하는 알고리즘의 수정된 버전은 다음과 같습니다.

public static int[] removeDuplicatesWithoutSet(int[] arr) {

    HashMap<Integer, Boolean> map = new HashMap<>();
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        if (map.containsKey(arr[i])) {
            int shiftLeft = i;
            for (int k = i + 1; k < end; k++, shiftLeft++) {
                arr[shiftLeft] = arr[k];
            }
            end--;
            i--;
        } else {
            map.put(arr[i], true);
        }
    }

    int[] whitelist = new int[end];
    for (int i = 0; i < end; i++) {
        whitelist[i] = arr[i];
    }
    return whitelist;
}

위 내용은 세트를 사용하지 않고 배열에서 중복 항목을 효율적으로 제거하려면 어떻게 해야 합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!