Найти K ближайших точек к центру

У нас есть массивpoints, в котором хранятся координаты точек на декартовой поверхности. Найи K точек ближайшик к центру (0, 0).

(Здесь мы имеем в виду, что расстояние между точками Евклидово)

Можно вернуть список ближайших точек отсортированных в любом порядке. Ответ гарантированно существует и единственнй.

Пример 1:

Дано: points = [[1,3],[-2,2]], K = 1
Результат: [[-2,2]]
Пояснение: 
Расстояние между (1, 3) и нулевой точкой = sqrt(10).
Расстояние между (-2, 2) и нулевой точкой = sqrt(8).
Поскольку sqrt(8) < sqrt(10), (-2, 2) - ближайшая точка.
Нам нужно найти только K = 1 блиайших точек, поэтому в ответе только [[-2,2]].

Пример 2:

Дано: points = [[3,3],[5,-1],[-2,4]], K = 2
Результат: [[3,3],[-2,4]]
(Ответ [[-2,4],[3,3]] тоже принимается.)

Примечания:

1. 1 <= K <= points.length <= 10000
2. -10000 < points[i][0] < 10000
3. -10000 < points[i][1] < 10000


Идея решения

Идея достаточно проста:

• создать массив расстояний от каждой точки до нулевой;
• отсортировать его;
• взять K-е из самых коротких расстояний;
• пройтись по массиву с точкам и сравнить, не превосходит ли расстояние каждой точки это K-е расстояние.
  

Имплементация

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        int N = points.length;
        int[] dists = new int[N];
        for (int i = 0; i < N; ++i)
            dists[i] = dist(points[i]);

        Arrays.sort(dists);
        int distK = dists[K-1];

        int[][] ans = new int[K][2];
        int t = 0;
        for (int i = 0; i < N; ++i)
            if (dist(points[i]) <= distK)
                ans[t++] = points[i];
        return ans;
    }
    
     public int dist(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

Сложность

• Сложность по времени: $O(Nlog N)$, где $N$ - это длинна массива points.

• Сложность по памяти: $O(N)$.