Преобразуйте набор координат в упорядоченный 2D массив

#algorithm #sorting #multidimensional-array #coordinates

Вопрос:

Предположим, у меня есть набор из n координат (x, y), например (123, 41), (123, 50), (555, 10), (600, 10)

И я хотел преобразовать его в 2D массив, где:

Количество столбцов равно уникальному числу координат x
Количество строк равно уникальному числу координат y
Никакие два набора координат не будут точно одинаковыми, и нет никаких ограничений на то, какими могут быть значения x и y.
Координата размещается в индексах относительно x и y всех остальных координат. Например, (555,10) имеет вторую по величине координату x (x=1) и одну из наименьших координат y (y=0), поэтому ее положение будет [1][0]

x=0 x=1 x=2

y=0 нулевой (555, 10) (600, 10)

y=1 (123, 41) нулевой нулевой

y=2 (123, 50) нулевой нулевой

	x=0	x=1	x=2
y=0	нулевой	(555, 10)	(600, 10)
y=1	(123, 41)	нулевой	нулевой
y=2	(123, 50)	нулевой	нулевой

(Существует 3 уникальных координаты x (123, 555, 666) и 3 уникальных координаты y (41, 50, 10), поэтому массив 3×3)

Какой алгоритм я могу использовать для создания 2D-массива из набора координат, как описано выше? Я попытался создать свой собственный, но это очень медленно, когда n очень большое O(n^2).

1. Пожалуйста, укажите ограничения проблемы. сколько баллов можно набрать максимум? Если (x, y) есть какая-либо допустимая координата, насколько она велика x или y может быть? Будет x и y всегда будет меньше, чем n где n — количество вводимых точек?

2. @AKSingh Отредактировал спасибо.

3. Вы должны указать диапазон n как в 1 <= n Также x будет меньше, чем n 1 <= x <= n ?

Ответ №1:

Вот простое решение:

Получите все данные и координаты и отсортируйте их. x y
Для каждой точки получите ее положение x и y координаты в соответствующих отсортированных массивах. Поместите точку в эту позицию в результирующем массиве.

Что-то вроде этого (на Python):

 # cook your dish here
points = [(123, 41), (123, 50), (555, 10), (600, 10)]
x_coords = sorted(list(set(i[0] for i in points))) # all distinct x coordinates
y_coords = sorted(list(set(i[1] for i in points))) # all distinct y coordinates
result = [[0 for i in range(len(x_coords))] for j in range(len(y_coords))]

for i in points:
    x_final = x_coords.index(i[0])
    y_final = y_coords.index(i[1])
    result[y_final][x_final] = i
    
for i in result:
    print(i)

Это дает:

 [0, (555, 10), (600, 10)]
[(123, 41), 0, 0]
[(123, 50), 0, 0]

Вы можете заменить нули на None или null в соответствии с вашим удобством.
Этот метод имеет O(NlogN) временную сложность.

Изменить: index() метод может быть не самым эффективным способом в зависимости от используемого языка/структуры данных. Вы можете использовать двоичный поиск для реализации того же самого.