O (log (n))의 움직이는 창에서 최대/최소 파인더를 생성해야하는이 학교 과제가 있습니다. 할당은 java 클래스 java.util.TreeMap 또는 큐를 구현에 사용하는 힌트를 제공합니다. 지금까지는 대기열을 사용하여 O (n)에서 작동하는 작업 코드 만 만들 수있었습니다. Under는 treeMap을 사용하여 지금까지 수행 한 작업이지만 treeMap 클래스를 이해하는 데 문제가 있습니다. 나는 사용할 올바른 도구를 찾지 못하는 것 같습니다. 이제는 가장 초기 값이 아니라 가장 큰 값을 제거합니다. 값과 인덱스를 쌍으로 만들려고했으나 가장 큰 값을 찾기 위해 값을 비교할 수 없었습니다.O (log (n))에서 움직이는 창의 최소/최대 찾기
누군가 내가이 일로 나를 앞으로 나아가게 할 수 있다면 나는 기뻐할 것이다.
readTreeMap 설명서가 있습니까?
Red-Black 트리 기반 NavigableMap 구현. 맵은, 키의 「자연 순서 붙이고」에 따라, 또는 사용되는 생성자에 응해, 맵 작성시에 제공된 Comparator에 의해 소트됩니다.
이 구현은 containsKey, get, put 및 remove 조작에 대한 보증 된 log (n) 시간을 제공합니다. 알고리즘은 Cormen, Leiserson 및 Rivest의 알고리즘 소개에있는 알고리즘을 적용한 것입니다.
따라서 정렬 된 데이터 구조입니다. 그것은 말할 것도 없지만 firstKey과 lastKey은 일정 시간 또는 O (로그 N)이라고 가정 할 수 있습니다. 따라서 put, firstKey, lastKey 및 remove 중 네 가지를 호출하면 O (로그 N) 바운드가됩니다.
이 작업을 수행하려면 트리 맵 생성자에게 키 정렬 방법에 대한 힌트를 제공해야합니다. 여기에 암시 적 변환 매개 변수 A => Ordered[A] 및 TreeMap 생성자 (이 매개 변수에 대해 알지 못하는)를 요구하는 스칼라간에 불일치가 조금 있습니다. 따라서 "키의 자연 순서를 사용합니다." 또는 귀하의 경우에 맞지 않을 수도 있습니다.
키가 올바르게 정렬되도록하려면 A <: Comparable을 지정하거나 Comparator을 명시해야합니다.
키와 값과 같은 값을 저장하고 값을 사용하지 않으므로 TreeMap[A, Unit] 또는 실제로는 TreeSet이 될 수 있습니다. collection.mutable.SortedSet과 같이 적절한 스칼라 컬렉션을 얻으려면 java.util.TreeMap을 바꿀 수도 있습니다. 이렇게하면 Ordering[A] (소위 유형 클래스)의 인스턴스를 통해 순서가 지정됩니다. 동일한 메소드 firstKey과 lastKey을 가지고 있습니다.
힌트 : 슬라이드 창으로서 가장 오래된 값을 제거하는 빠르고, 또한 첫 번째 또는 마지막 요소의 제거를 갖는 제 2 데이터 구조를 유지하는데 아무런 문제가 없다. 귀하의 질문에이 데이터 구조에 대해서도 언급되어 있습니다.
나는 그 Comparator의 개념을 이해하지만 어떻게 구현하는지 이해할 수 없다. (나는 오류 만 받는다.) – Jezzie
나는 거의 그것을 만들었다. 문제는 만약 당신이 같은 값을 두 번 더하면 두 개의 인스턴스로 계산하지 않는다는 것입니다 : ( – Jezzie
@Jezzie 그러면 [A, Int]를 Map으로 사용할 수 있습니다. –