Created
May 30, 2020 11:09
-
-
Save Gowtham-369/b7cad86f93afe360ce0dd3905ea3b65a to your computer and use it in GitHub Desktop.
Day 30 : LeetCode 30 Day May Challenges
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //always STL generally takes extra space than arrays | |
| //better use them | |
| class Solution { | |
| public: | |
| int distance(vector<int>& v){ | |
| return v[0]*v[0]+v[1]*v[1]; | |
| } | |
| vector<vector<int>> kClosest(vector<vector<int>>& points, int K) { | |
| //for all points in points ,calculate distances and store it in array | |
| //sort it and get distance of kth nearest point | |
| //now traverse again points array and pick those points whose distance <= distk | |
| int n = points.size(); | |
| vector<int> dists(n); | |
| for(int i=0; i<n; i++){ | |
| dists[i] = distance(points[i]); | |
| } | |
| sort(dists.begin(),dists.end()); | |
| int distK = dists[K-1];//Kth nearest distance | |
| vector<vector<int>> ans(K); | |
| int cnt = 0; | |
| for(auto x:points){ | |
| if(cnt == K) | |
| break; | |
| if(distance(x) <= distK){ | |
| ans[cnt] = x; | |
| cnt++; | |
| } | |
| } | |
| return ans; | |
| /* | |
| map<int,vector<vector<int>>> mp; | |
| //points are mapped to their diatances | |
| //we can have multiple points with same distance,so array of points are mapped to distance | |
| //instead of sqrt() of distance,we can use without sqrt | |
| for(auto x:points){ | |
| mp[(x[0]*x[0]+x[1]*x[1])].push_back(x); | |
| } | |
| int cnt = 0; | |
| vector<vector<int>> ans(K); | |
| //0 to k-1 cells | |
| for(auto it = mp.begin(); it!=mp.end(); it++){ | |
| if(cnt == K) | |
| break; | |
| for(auto x:(it->second)){ | |
| //it->second is 2D vector/array | |
| //auto can be vector<int> | |
| //ans.push_back(x); | |
| ans[cnt] = x; | |
| cnt++; | |
| } | |
| } | |
| return ans; | |
| */ | |
| } | |
| }; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 <= K <= points.length <= 10000 | |
| -10000 < points[i][0] < 10000 | |
| -10000 < points[i][1] < 10000 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment