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

세트 없이 효율적인 배열 중복 제거

일부 프로그래밍 문제에서는 사전 구축된 값을 활용하지 않고 배열에서 중복된 값을 제거해야 할 수도 있습니다. Set 또는 HashSet과 같은 데이터 구조. 고려할 수 있는 최적화된 접근 방식은 다음과 같습니다.

제공된 구현은 어레이에 대해 여러 패스를 수행하므로 시간이 비효율적으로 복잡해집니다. 이를 개선하려면 두 가지 최적화 조합을 사용하는 것을 고려해 보십시오.

1. 마커 배열 사용:

원래 배열의 최대 요소와 동일한 크기의 마커 배열을 만듭니다. 모든 요소를 ​​0으로 초기화합니다. 원본 배열에서 요소를 발견하면 마커 배열에서 해당 위치를 1로 설정합니다. 이렇게 하면 요소가 중복되었는지 여부를 확인하기 위해 마커 배열만 확인하면 됩니다.

2. 끝 인덱스 포인터 사용:

중복 항목이 없는 배열이 계산된 인덱스를 나타내는 끝 인덱스 포인터를 유지합니다. 중복 항목이 발견되면 중복 항목 뒤의 요소를 왼쪽으로 이동하고 그에 따라 끝 인덱스를 줄입니다.

다음은 이러한 최적화를 사용하여 최적화된 코드 버전입니다.

public static int[] removeDuplicates(int[] arr) {
    // Initialize the marker array with zeros
    int[] marker = new int[1000000];
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        // Check if the element is already marked as duplicate
        if (marker[arr[i]] == 1) {
            // If it's a duplicate, shift the elements after it to the left
            for (int j = i + 1; j < end; j++, i++) {
                arr[i] = arr[j];
            }
            end--;
            i--;
        } else {
            // If it's not a duplicate, mark it in the marker array
            marker[arr[i]] = 1;
        }
    }

    return arr;
}

이 구현은 어레이에 대한 다중 패스를 방지하고 필요한 요소 교체 횟수를 줄여 성능을 크게 향상시킵니다.

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