973. K Closest Points to Origin

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
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000
A acceptable but definitely no the best solution….
In PHP:
  1. a ** b means power (a,b)
  2.  <=>, the spaceship operator,  used by ‘comparator’
    1. if left < right return -1
    2. if left > right return 1
    3. if left == right return 0
class Solution {

    /**
     * @param Integer[][] $points
     * @param Integer $K
     * @return Integer[][]
     */
    function kClosest($points, $K) {
        usort($points, function ($a, $b){
            return ($a[0]**2 + $a[1]**2) <=> ($b[0]**2 + $b[1]**2);
        });
        
        $result = [];
        $i = 0;
        foreach($points as $p){
            if($i >= $K){
                break;   
            }
            $result[] = $p;
            $i ++;
    
        }
        return $result;
    }
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.