-5
큰 범위의 범위가 있다고 가정 해 보겠습니다. 예를 들어 크기가 5000 세트 : 정수 n이 효율적으로 자바에서 이러한 범위 중 적어도 하나에 떨어지면정수가 주어진 범위의 집합에 있는지 확인하는 방법은 무엇입니까?
[100,200],[1,59],[3,5],[70,70]...
를 확인하는 방법?
A
답변
5
이 작업을 효율적으로 수행하는 방법은 Bitset을 만들어 모든 세트의 모든 정수에 대해 비트를 설정하는 것입니다. 그런 다음 하나의 O(1) 통화로 회원 자격을 테스트 할 수 있습니다.
정수의 결합 된 범위가 크면 Bitset은 많은 메모리를 차지할 것입니다.
두 번째 방법은 겹치는 범위를 결합하여 TreeMap<Integer, Integer>을 구성하는 것입니다. 여기서 키는 하한이고 값은 각 결합 된 범위의 상한입니다. 그런 다음 TreeMap::floorKey과 테스트를 사용하여 일치하는 범위를 찾습니다. 이 절차는 O(logN)입니다. 여기서 N은 결합 된 범위의 수입니다. 공간 사용량은 O(N)입니다.
+1
두 번째 방법의 대안은 [Guava의'RangeSet'] (https://google.github.io/guava/releases/21.0/api/docs/com/google/common/collect/RangeSet.html)과 같은 것을 사용하는 것입니다.). 범위를 결합하고 포함 된 값을 쿼리하는 것에서 조금 힘들게됩니다. –
왜이 질문에 파이썬 태그가 있습니까? –
이러한 범위는 어떤 개체로 나타 납니까? 길이 2 또는 범위 클래스의 정수 배열? – Zachary
겹치는 범위를 병합 한 다음 정렬합니다. 이진 검색을 사용하여 테스트 값이 포함되어 있는지 확인하십시오. 또는 도메인이 비교적 작은 경우, 비트 100-200, 1-59 등이 모두 설정된 BitSet을 빌드하고'bitset.get (testValue) '를 사용하십시오. –