973. K Closest Points to Origin

leetcode medium

#array#csharp#leetcode#math#medium#sort

Task

Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0).

Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)).

Вы можете вернуть ответ в любом порядке. Гарантируется, что ответ будет уникальным (за исключением порядка).

Пример:

Input: points = [[1,3],[-2,2]], k = 1

Output: [[-2,2]]

Explanation:

The distance between (1, 3) and the origin is sqrt(10).

The distance between (-2, 2) and the origin is sqrt(8).

Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.

We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int[][] KClosest(int[][] points, int k) {
        Array.Sort(points, (a, b) => SquaredDistance(a).CompareTo(SquaredDistance(b)));
        var result = new int[k][];
        Array.Copy(points, result, k);
        return result;
    }
    private int SquaredDistance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int[][] KClosest(int[][] points, int k) {
        Array.Sort(points, (a, b) => SquaredDistance(a).CompareTo(SquaredDistance(b)));
        var result = new int[k][];
        Array.Copy(points, result, k);
        return result;
    }
    private int SquaredDistance(vector<int>& point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

Java solution

matched/original

import java.util.Arrays;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
        return Arrays.copyOfRange(points, 0, k);
    }

    private int squaredDistance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

JavaScript solution

matched/original

class Solution {
    kClosest(points, k) {
        points.sort((a, b) => this.squaredDistance(a) - this.squaredDistance(b))
        return points.slice(0, k)
    }

    squaredDistance(point) {
        return point[0] * point[0] + point[1] * point[1]
    }
}

Python solution

matched/original

class Solution:
    def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
        points.sort(key=self.squaredDistance)
        return points[:k]

    def squaredDistance(self, point: list[int]) -> int:
        return point[0] ** 2 + point[1] ** 2

Go solution

matched/original

import (
    "sort"
)

func kClosest(points [][]int, k int) [][]int {
    sort.Slice(points, func(i, j int) bool {
        return squaredDistance(points[i]) < squaredDistance(points[j])
    })
    return points[:k]
}

func squaredDistance(point []int) int {
    return point[0]*point[0] + point[1]*point[1]
}

Explanation

Algorithm

Отсортируйте массив с помощью функции компаратора.

Функция компаратора будет использовать уравнение квадратного евклидова расстояния для сравнения двух точек.

Верните первые k элементов массива.

😎