{"id":4626,"date":"2019-01-13T01:37:16","date_gmt":"2019-01-13T09:37:16","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4626"},"modified":"2019-01-13T11:21:27","modified_gmt":"2019-01-13T19:21:27","slug":"leetcode-973-k-closest-points-to-origin","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-973-k-closest-points-to-origin\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 973. K Closest Points to Origin"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 973. K Closest Points to Origin - \u5237\u9898\u627e\u5de5\u4f5c EP240\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/zWiB3RGa-vo?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>We have a list of&nbsp;<code>points<\/code>&nbsp;on the plane.&nbsp; Find the&nbsp;<code>K<\/code>&nbsp;closest points to the origin&nbsp;<code>(0, 0)<\/code>.<\/p>\n\n\n\n<p>(Here, the distance between two points on a plane is the Euclidean distance.)<\/p>\n\n\n\n<p>You may return the answer in any order.&nbsp; The&nbsp;answer is guaranteed to be unique (except for the order that it is in.)<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>points = [[1,3],[-2,2]], K = 1 <br><strong>Output: <\/strong>[[-2,2]] <br><strong>Explanation: <\/strong> 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) &lt; 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]]. <\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>points = [[3,3],[5,-1],[-2,4]], K = 2 <br><strong>Output: <\/strong>[[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.) <\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>1 &lt;= K &lt;= points.length &lt;= 10000<\/code><\/li><li><code>-10000 &lt; points[i][0] &lt; 10000<\/code><\/li><li><code>-10000 &lt; points[i][1] &lt; 10000<\/code><\/li><\/ol>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-1.png\" alt=\"\" class=\"wp-image-4636\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-2.png\" alt=\"\" class=\"wp-image-4635\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-3.png\" alt=\"\" class=\"wp-image-4634\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-4.png\" alt=\"\" class=\"wp-image-4633\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/01\/973-ep240-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Sort<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, Running time: 180 ms\nclass Solution {\npublic:\n  vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {    \n    vector<long> s(points.size());\n    for (int i = 0; i < points.size(); ++i)\n      s[i] = (static_cast<long>(points[i][0] * points[i][0] + \n                                points[i][1] * points[i][1]) << 32) | i;\n    std::sort(begin(s), end(s));\n    \n    vector<vector<int>> ans(K);\n    for (int i = 0; i < K; ++i)\n      ans[i] = points[static_cast<int>(s[i])];\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua, running time: 528 ms\nclass Solution:\n  def kClosest(self, points, K):\n    return sorted(points, key = lambda p: p[0]**2 + p[1]**2)[0:K]\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>We have a list of&nbsp;points&nbsp;on the plane.&nbsp; Find the&nbsp;K&nbsp;closest points to the origin&nbsp;(0, 0). (Here, the distance between two points on a plane is the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127],"tags":[222,284,31,15],"class_list":["post-4626","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-easy","tag-geometry","tag-math","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4626","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4626"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4626\/revisions"}],"predecessor-version":[{"id":4639,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4626\/revisions\/4639"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4626"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4626"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4626"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}