Java 배열에서 중복된 정수를 어떻게 효율적으로 찾을 수 있습니까?

Java 배열에서 중복 항목 찾기

문제

정수 배열이 있고 중복 항목을 효율적으로 식별하려고 합니다. 각 요소 쌍을 비교하려고 시도하는 초기 코드는 존재하지 않는 중복 항목을 정확하게 감지하지 못합니다.

문제

코드의 결함은 초기화되는 중복 플래그에 의존한다는 것입니다. 모든 경우에 거짓이 됩니다. 중복 항목이 발견되지 않은 경우에도 루프는 대각선 요소를 확인할 때(예: j == k인 경우) 중복 항목을 true로 설정합니다.

더 미묘한 솔루션

이 문제를 해결하려면 다음을 확인하세요. 중복 플래그는 실제 중복이 발견된 경우에만 true로 설정됩니다. 이는 j == k일 때 zipcodeList[j] 자체와의 비교를 생략하여 달성할 수 있습니다.

수정된 코드는 다음과 같습니다.

duplicates = false;
for (int j = 0; j < zipcodeList.length; j++) {
    for (int k = 0; k < zipcodeList.length; k++) {
        if (k != j && zipcodeList[k] == zipcodeList[j]) {
            duplicates = true;
        }
    }
}

더 빠른 접근 방식

위 솔루션의 런타임 복잡도는 O(n²)입니다. 여기서 n은 배열의 요소 수입니다. 대규모 어레이의 경우 이 접근 방식은 비효율적일 수 있습니다.

중복을 검색하는 보다 효율적인 방법은 해시 기반 접근 방식을 활용하여 시간 복잡도를 O(n)으로 줄이는 것입니다. 다음은 HashSet을 사용하는 예입니다.

boolean duplicates(int[] zipcodeList) {
    Set<Integer> lump = new HashSet<>();
    for (int zipcode : zipcodeList) {
        if (lump.contains(zipcode)) {
            return true;
        }
        lump.add(zipcode);
    }
    return false;
}

또는 boolean[] 배열(비트맵)을 사용하여 O(n) 솔루션을 달성하여 이전에 발견된 요소를 추적하고 요소가 있을 때 중복을 true로 설정할 수 있습니다. 두 번째로 만났습니다.

결론

입력 배열의 크기와 빈도에 따라 중복된 경우 효율성을 최적화할 수 있도록 접근 방식 선택을 맞춤화해야 합니다.

위 내용은 Java 배열에서 중복된 정수를 어떻게 효율적으로 찾을 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!