>  기사  >  Java  >  Java 배열에서 반복되는 숫자에 대한 쿼리를 구현하는 방법

Java 배열에서 반복되는 숫자에 대한 쿼리를 구현하는 방법

不言
不言앞으로
2018-10-23 15:14:263621검색

이 기사의 내용은 Java에서 배열의 반복되는 숫자에 대한 쿼리를 구현하는 방법에 대한 것입니다. 특정 참조 값이 있으므로 도움이 되길 바랍니다.

질문 1: 배열에서 반복되는 숫자를 찾으세요.

길이가 N인 배열의 모든 숫자는 0-n-1 범위 내에 있습니다. 배열의 일부 숫자가 반복되지만 몇 개의 숫자가 반복되는지는 모르겠습니다. 숫자가 몇 번 반복되는지 알 수 없습니다. 배열에서 반복되는 숫자를 찾아보세요.

해결책 1: 이 배열을 정렬합니다. 정렬된 배열에서 중복된 숫자를 찾는 것은 매우 쉽습니다. 정렬된 배열을 처음부터 끝까지 스캔하면 길이 N의 배열을 정렬하는 데 O(nLogn) 시간이 필요합니다.

해결 방법 2: 문제 해결을 위해 해시 테이블을 사용합니다. 숫자를 스캔할 때마다 해당 숫자가 해시 테이블에 있는지 확인합니다. 이 알고리즘의 시간은 O(N)이지만 시간 효율성은 O(N) 크기의 해시 테이블을 희생하면서 발생합니다.

해결책 3: 이 배열을 재배열하고 이 배열의 각 숫자를 처음부터 끝까지 스캔합니다. 아래 첨자 i가 있는 숫자를 스캔할 때 이 숫자의 값(m)이 i와 같은지 비교합니다. 동일하면 m의 값을 i에 지급하고, 동일하지 않으면 반복되는 값을 모두 찾을 때까지 m의 첨자에 해당하는 값과 비교한다.

Java 배열에서 반복되는 숫자에 대한 쿼리를 구현하는 방법

위 내용은 Java 배열에서 반복되는 숫자에 대한 쿼리를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
이 기사는 segmentfault.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제