Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.org

README.org

Leetcode: K Closest Points to Origin


K Closest Points to Origin


Similar Problems:


We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

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]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/k-closest-points-to-origin
// Basic Idea: sort
// Complexity: Time O(n*log(n)), Space O(n)
import "sort"
type Point struct {
    i int
    v int
}
func kClosest(points [][]int, K int) [][]int {
    l := []Point{}
    for i, p := range points {
        l = append(l, Point{i, p[0]*p[0]+p[1]*p[1]})
    }
    sort.Slice(l, func(i, j int) bool {
      return l[i].v < l[j].v
    })

    res := [][]int{}
    for i := K-1; i>=0; i-- {
        res = append(res, points[l[i].i])
    }
    return res
}
linkedin
github
slack