K Ближайшие точки к заданной целевой точке

Дан список точек на двумерной плоскости arr[][] , заданная точка target и целое число K . Задача состоит в том, чтобы найти K ближайших к цели точек из заданного списка точек.

Примечание . Расстояние между двумя точками на плоскости называется евклидовым расстоянием.

Примеры:

Input: points = [[3, 3], [5, -1], [-2, 4]], target = [0, 0], K = 2
Output: [[3, 3], [-2, 4]]
Explanation: Square of Distance of target(=origin) from this point is
(3, 3) = 18
(5, -1) = 26
(-2, 4) = 20
So the closest two points are [3, 3], [-2, 4].

Input: points = [[1, 3], [-2, 2]], target = [0, 1], K  = 1
Output: [[1, 3]]

Подход: решение основано на жадном подходе. Идея состоит в том, чтобы вычислить евклидово расстояние от цели для каждой заданной точки и сохранить их в массиве. Затем отсортируйте массив по найденному евклидову расстоянию и выведите первые k ближайших точек из списка.

Ниже приведена реализация вышеуказанного подхода.

Временная сложность: O(N * logN)
Вспомогательное пространство: O(N)