https://leetcode.com/problems/k-closest-points-to-origin/

1. Use sort:

  1. //364 ms    63.7 MB
  3. class Solution {
  4. public:
  5.     vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
  6.         vector<int> distances;
  8.         for(int i = 0; i < points.size(); i++){
  9.             distances.push_back(distance(points[i]));
  10.         }
  12.         sort(distances.begin(), distances.end());
  13.         int distK = distances[K-1];
  16.         vector<vector<int>> result;
  18.         for(int i = 0; i < points.size(); i++){
  19.             if(distance(points[i]) <= distK){
  20.                 result.push_back(points[i]);
  21.             }
  22.         }
  24.         return result;
  25.     }
  27. private:
  28.     int distance(vector<int> point){
  30.         int dist = (point[0]*point[0]) + (point[1]*point[1]);
  32.         return dist;
  33.     }
  34. };

Time Complexity: O(N log N)
Space Complexity: O(N)