Как найти y, когда x задан, и список точек?

Question

Там есть группа:

S = {(xi,yi)|1 ≤ i ≤ n} 

из п точек. Нет 2 балла (xi,yi) (xj,yj) where xi = xj and yi = yj. Это означает, что значения x и y уникальны. Мне нужно найти структуру данных, которая поддерживает следующие функции:

1. Принято x, возвращает значение y, где (x, y) находится в S. Если оно не существует, возврат «не существует».
2. Учитывая y, верните значение x, где (x, y) находится в S. Если он не существует, возврат «не существует».

Простым решением будет создание двух отсортированных массивов (один из которых сортируется в соответствии со значениями x, а второй сортируется в соответствии с значениями y). Чтобы найти y с заданным x, возьмет O(logn), используя двоичный поиск. То же самое для нахождения x.

Я не могу использовать более одного массива (из n элементов), и каждый элемент является точкой. Мне нужно найти эффективную структуру данных, которая может делать эти действия в оптимальное время. Мне нужно найти:

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

Какая структура данных является наиболее эффективной в этом случае?

спасибо.

Answer 1

Фундаментально, вам просто нужна пара карт:

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

Вы можете использовать любую конкретную реализацию Map, например HashMap, TreeMap, LinkedHashMap ...

Чтобы добавить точку, вы просто добавить его как:

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

И вы можете получить y в течение x с помощью:

TypeOfY y = mapXtoY.get(x); 

и наоборот.

Библиотеки, такие как Guava, предоставляют BiMap реализации, которые поддерживают это двунаправленное сопоставление для вас.

Answer 2

Примечание: Я не прочитал ваше состояние '! (Хи уг), (хи, YJ) => Xi = Xj & & уг = YJ', как ты, мне это только означает, что координаты являются уникальными (не каждый x и каждый y).

Таким образом, вы должны сначала создать объект точки

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

Затем сохранить все точки в уникальный массив (вы сказали, что это нужно)

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

Наконец обернуть THS массив в класс, предоставляет методы, в которых вы нуждаетесь

public class PointCollection { 
    public Point[] points; 
    public Map<Integer, List<Integer>> mapX = new HashMap<Integer; List<Integer>>(); 
    public Map<Integer, List<Integer>> mapY = new HashMap<Integer; List<Integer>>(); 
    public PointCollection(Points[] points) { 
     this.points = points; 
     for (Point p : points) { 
      mapX.getOrDefault(p.x, new ArrayList<Integer>()).add(p.y); 
      mapY.getOrDefault(p.y, new ArrayList<Integer>()).add(p.x); 
     }  
    } 

    public int[] getMatchingY(int x) { 
     List<Integer> result = new ArrayList<Integer>(); 
     for (Point p : this.points)) { 
      if (p.x == x) result.add(p.y); 
     } 
     return result.toArray(new int[result.size()]); 
    } 

    public int[] getMatchingX(int y) { 
     List<Integer> result = new ArrayList<Integer>(); 
     for (Point p : this.points)) { 
      if (p.y == y) result.add(p.x); 
     } 
     return result.toArray(new int[result.size()]); 
    } 

    public int[] getMatchingYFromMap(int x) { 
     List<Integer> result = mapX.getOrDefault(x, new ArrayList<Integer>()); 
     return result.toArray(new int[result.size()]); 
    } 

    public int[] getMatchingXFromMap(int y) { 
     List<Integer> result = mapY.getOrDefault(y, new ArrayList<Integer>()); 
     return result.toArray(new int[result.size()]); 
    } 
} 

Редактировать: добавлено решение на основе карты