LeetCode Ts-973. K Closest Points to Origin

    AllenLi
    CodingLeetCode Js-Array

    Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
    The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 – x2)2 + (y1 – y2)2).
    You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

    給予一個點位置的陣列 points[i] = [xi, yi]，其中 points[i] 表示 X-Y 平面上的一個點，以及一個整數 k，回傳距離原點 (0, 0) 最接近的 k 個點。
X-Y 平面上兩點之間的距離為 √(x1 - x2)2 + (y1 - y2)2。
你可以二任意順序回傳答案，且答案保證為唯一。

    Example 1:

    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]].

    Example 2:

    Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.

    Solution:
    這題題目要求給了我們 x, y 軸的點，
    然後請我們找出 k 個與原點(0, 0)距離最近的點。
    我們先從 points 提供的 a, b 兩點求出距離 distance，
    並且將這個陣列做排序，
    最後再從最短的距離依序取出 k 個組合即可，
    記得題目只要點位，所以用 map 把距離移除。

    Code 1: BigO(n log n)

    function kClosest(points: number[][], k: number): number[][] {
    const arr: [number, number, number][] = [];
    for (const [a, b] of points) {
        const distance: number = a ** 2 + b ** 2;
        arr.push([distance, a, b]);
    }
    arr.sort((a, b) => a[0] - b[0]);
    const result: number[][] = arr.slice(0, k).map(([_, a, b]) => [a, b]);
    return result;
};

    FlowChart:
    Example 1

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

arr [ [ 10, 1, 3 ], [ 8, -2, 2 ] ]
arrSorted [ [ 8, -2, 2 ], [ 10, 1, 3 ] ]

return result; // [ [ -2, 2 ] ]

    Example 2

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

arr [ [ 18, 3, 3 ], [ 26, 5, -1 ], [ 20, -2, 4 ] ]
arrSorted [ [ 18, 3, 3 ], [ 20, -2, 4 ], [ 26, 5, -1 ] ]

return result; // [ [ 3, 3 ], [ -2, 4 ] ]

    Related Posts