트리 맵 : 키 값

Question

과 함께 움직이는지도의 정렬 값 난 다음 트리 맵이 있습니다

TreeMap<Integer, Double> map; 

더블 값이 고유하지 않습니다를.

정수 키와 firstEntry() 및 higherEntry() 함수를 사용하여 맵을 반복하고 Double 값을 수정하십시오.

이제 Double 값이 감소하는 순서로 쌍의 값을 나열하려고합니다. 이 작업을 수행하는 가장 좋은 방법은 무엇입니까?

정수 키가 중요하며 Double 값이 고유하지 않기 때문에 Double 키를 사용할 수 없습니다.

업데이트 : 자세한 설명 고전적인 문제입니다. 학생들의 두루마리가 열쇠이고 그들의 백분율이 가치라고 말할 수 있습니다. 이제 백분율을 기준으로 정렬 한 다음 우리는 누구의 비율인지 말할 수 있어야합니다. 그러므로 정수형 키가 필요합니다.

Answer 1

당신은 삽입 순서를 보장하는하는 TreeSet을 구축 할 수 있습니다 :

@Test 
public void treeMapSortedByValue() { 
    // given the following map: 
    TreeMap<Integer, Double> map = new TreeMap<Integer, Double>(); 
    map.put(2, Math.E); 
    map.put(1, Math.PI); 
    map.put(3, 42.0); 

    // build a TreeSet of entries 
    Set<Map.Entry<Integer, Double>> sortedEntries = new TreeSet<Map.Entry<Integer, Double>>(new DoubleComparator()); 
    sortedEntries.addAll(map.entrySet()); 

    // optionally you can build a List<Double> with the sorted 
    List<Double> doubles = new LinkedList<Double>(); 
    for (Map.Entry<Integer, Double> entry : sortedEntries) { 
     doubles.add(entry.getValue()); 
    } 
} 

이 당신을 제공해야합니다 : [2.718281828459045, 3.141592653589793, 42.0] (NB : [Math.E, Math.PI, Math.UNIVERSAL_ANSWER] :-)를.

PS

Comparator :

class DoubleComparator implements Comparator<Map.Entry<Integer, Double>> { 

    @Override 
    public int compare(Entry<Integer, Double> o1, Entry<Integer, Double> o2) { 
     return Double.compare(o1.getValue(), o2.getValue()); 
    } 
} 

Answer 2

다음 작업을 수행 할 수 있습니다. entrySet을 사용하여 항목을 반복합니다. 목록에 넣으십시오. 그런 다음 오른쪽 비교 자로 날짜를 정렬하십시오. , 그들을 정렬 진행 (Collections.sort를 사용하거나 -

은

Answer 3

확실한 해결책은 (당신은 그냥 사용할 수있는 트리 맵 클래스는 values() 방법이있는 entrySet 다음 getValue를 통해 가능 ) 복식의 컬렉션을 얻는 것입니다 Arrays.sort) - 이것은 O (n logn) 시간이 걸립니다.

데이터 구조를 완전히 변경하지 않는 한 더 똑똑한 (== 빠른) 방법으로 수행 할 수 있을지 확신하지 못합니다. 그러나 다른 데이터 구조에서이 문제가 발생하는 것을 보는 유일한 방법은 정수 및 double에 대한 래퍼를 유지하고 두 개의 비교자를 작성하는 것입니다. integer과 첫 번째로 double을 비교 한 다음 integer으로 비교합니다. 사용하고있는 원래의 TreeMap은 동일하지만 두 번째 비교기로 정렬하여 다른 TreeMap을 분리 할 수 ​​있습니다. 분리해도 O (n logn) 시간이 걸릴 것입니다.