X verildiğinde ve bir nokta listesiyle nasıl bulunur? n noktalarının</p> <pre><code>S = {(xi,yi)|1 ≤ i ≤ n} </code></pre> <p>:

Question

bir grup var. 2 puanlık (xi,yi) (xj,yj) where xi = xj and yi = yj vardır. Bu, x ve y değerlerinin benzersiz olduğu anlamına gelir. o dönüş "yok" yoksa (x, y) S. olduğu,

1. Verilen x y değerini döndürür: Ben işlevlerini destekleyen bir veri yapısını bulmalıyız.
2. Verilen değer, x değerini (x, y) S olarak döndürür. Varsa, "yok" geri dönüşü.

Basit bir çözüm iki sıralı dizi oluşturmaktır (biri x değerlerine göre sıralanır ve ikinci olarak y değerlerine göre sıralanır). Verilen bir x ile y bulmak için ikili arama kullanarak O(logn) alacaktır. X bulmak için aynı.

Birden çok dizi (n öğesinden) kullanamıyorum ve her öğe numaralı noktadır. Bu eylemleri en uygun zamanda yapabilen verimli bir veri yapısı bulmalıyım. Bulmam gereken:

T(first function)+T(second action).

Bu durumda hangi veri yapısı en verimli?

Çok teşekkür ederim.

Map<TypeOfX, TypeOfY> mapXtoY; 
Map<TypeOfY, TypeOfX> mapYtoX; 

Sen Map herhangi somut uygulamasını kullanabilirsiniz, örneğin:

Answer 1

Temelde, sadece haritaların bir çift gerekir

void addPoint(TypeOfX x, TypeOfY y) { 
    mapXtoY.put(x, y); 
    mapYtoX.put(y, x); 
} 

Ve kullanarak bir x için y alabilirsiniz: HashMap, TreeMap, LinkedHashMap ...

bir nokta eklemek için tek yapmanız gereken hem eklemek

TypeOfY y = mapXtoY.get(x); 

ve tersi.

Guava gibi kitaplıklar sizin için bu iki yönlü eşlemeyi sürdüren BiMap uygulamalarını sağlar.

Answer 2

Not: Sizin gibi durumunuzu '! (Xi, yi), (xj, yj) => xi = xj & & yi = yj' okumak Yüklü bana bunu sadece koordinatlar benzersiz anlamına gelir (her x ve her y değil).

Yani ilk

public class Point { 
    public int x; 
    public int y; 
    public Point(int x, int y) { this.x = x; this.y = y; } 
} 

Sonra benzersiz bir diziye bütün puanlarınızı saklamak Bir Nokta nesnesi oluşturmanız gerekir

Point[] POINTS = ... // fill your array depending on your input 

Nihayet bir sınıfa ths dizisinin sarılmasıdır (dediğin İhtiyacınız) o gereksinim olan yöntemleri sağlar

düzenleme: ekli çözüm Haritada gör