가장 작은 키를 찾기위한 해시 테이블 역방향 조회

Question

해시 테이블에서 값을 검색하고 가장 작은 키를 반환하는 인터뷰 질문이 있습니다.

내 접근 방식은 해시 테이블을 키별로 정렬하고 검색된 값에 해당하는 키를 찾기 위해 반복합니다.

def smallestKey(x): 
    my_dict = {10:20, 5:30, -2:25, 1:20} 
    for key in sorted(dict.iterkeys()): 
     if (my_dict[key] == x): 
      print key 

더 나은 방법이 있나요 :

는 파이썬에서이 기능을 썼다? Java에서 어떻게 동일한 작업을 수행 할 수 있습니까?

Answer 1

만약 당신이 무엇을 검사하고 있는지, 그리고 어떤 유형의 키가 Number인지를 보장 할 수 있다면 기꺼이 할 수 있습니다.

다음은 코드 샘플입니다. 정렬 비용은 O (n log (n))이고 선형 검색은 O (n)이므로이 성능은 O (n log (n)) 정도입니다. 더 사용할 수있는 실제 사례가 될 수

public <K extends Number & Comparable<K>, V extends Number> K findSmallestKey(Map<K, V> values, V searchItem) { 
    // Grab the key set, and sort it. 
    List<K> keys = new ArrayList<>(values.keySet()); 
    Collections.sort(keys); 
    for(K key : keys) { 
     if(values.get(key).doubleValue() == searchItem.doubleValue()) { 
      return key; 
     } 
    } 
    return null; 
} 

구아바 offers BiMap; 그러나 중복 값을 덮어 쓰지 않고 중복 값을 허용하지 않습니다.

다음은 그 예입니다.

public <K extends Number, V extends Number> K findSmallestKeyWithBimap(BiMap<K, V> values, V searchItem) { 
    return values.inverse().get(searchItem); 
} 

그것은 많은 더 간결한, 그리고 이전 그랬던 것처럼 제네릭의 같은 종류를 필요로하지 않는다 (이 단지 Number하지 할 필요가 모두 Number 및 Comparable). 또한 유연성이 훨씬 떨어 지므로 그 특성으로 인해 키와 값 사이에 일대일 매핑이 명시 적으로 보장됩니다.