Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /******************************************************************************
- Online C++ Compiler.
- Code, Compile, Run and Debug C++ program online.
- Write your code in this editor and press "Run" button to compile and execute it.
- *******************************************************************************/
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <queue>
- using namespace std;
- struct Point {
- int x;
- int y;
- int distance;
- Point(int x, int y, int distance) : x(x), y(y), distance(distance) {}
- };
- struct Compare {
- bool operator() (Point p1, Point p2) {
- return (p1.distance < p2.distance);
- }
- } compare;
- struct CompareMinHeap {
- bool operator() (Point p1, Point p2) {
- return (p1.distance > p2.distance);
- }
- };
- struct CompareMaxHeap {
- bool operator() (Point p1, Point p2) {
- return (p1.distance < p2.distance);
- }
- };
- // Given a point P and other N points in two dimensional space, find K points out of the N points which are nearest to P.
- // Run-time complexity O(nlogn)
- /*
- vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
- vector<Point> distances;
- // O(n)
- for (int i = 0; i < points_set.size(); ++i) {
- int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
- Point np(points_set[i][0], points_set[i][1], dist);
- distances.push_back(np);
- }
- // O(nlogn) -- quick sort
- sort(distances.begin(), distances.end(), compare);
- vector<vector<int>> ans(k, vector<int> (2));
- // O(k)
- for (int i = 0; i < k; ++i) {
- vector<int> p = {distances[i].x, distances[i].y};
- ans[i] = p;
- }
- return ans;
- }
- */
- // Run-time complexity O(max(n, klogn)
- /*
- vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
- vector<Point> distances;
- // O(n)
- for (int i = 0; i < points_set.size(); ++i) {
- int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
- Point np(points_set[i][0], points_set[i][1], dist);
- distances.push_back(np);
- }
- // O(n)
- priority_queue<Point, vector<Point>, CompareMinHeap> pq(distances.begin(), distances.end());
- vector<vector<int>> ans(k, vector<int> (2));
- // O(klogn)
- for (int i = 0; i < k; ++i) {
- vector<int> p = {pq.top().x, pq.top().y};
- ans[i] = p;
- pq.pop(); //O(logn)
- }
- return ans;
- }
- */
- // Run-time complexity O(max(n, klogk, (n-k)logk)
- /*
- vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
- vector<Point> distances;
- // O(n)
- for (int i = 0; i < points_set.size(); ++i) {
- int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
- Point np(points_set[i][0], points_set[i][1], dist);
- distances.push_back(np);
- }
- // O(k)
- priority_queue<Point, vector<Point>, CompareMaxHeap> pq(distances.begin(), distances.begin() + k);
- vector<vector<int>> ans(k, vector<int> (2));
- // O((n-k)logk)
- for (int i = k; i < points_set.size(); ++i) {
- if (distances[i].distance < pq.top().distance) {
- pq.pop();
- pq.push(distances[i]);
- }
- }
- // O(klogk)
- for (int i = 0; i < k; ++i) {
- vector<int> p = {pq.top().x, pq.top().y};
- ans[i] = p;
- pq.pop(); //O(logk)
- }
- return ans;
- }
- */
- void PrintVector(const vector<Point>& vec) {
- for (Point p : vec) {
- std::cout << p.distance << " ";
- }
- std::cout << std::endl;
- }
- void HoareQuickSort(vector<Point>& vec, int left, int right, const int k) {
- if (k <= right - left + 1) {
- Point pivot = vec[right];
- int j = -1;
- for (int i = 0; i < vec.size() - 1; ++i) {
- if (vec[i].distance < pivot.distance)
- swap(vec[i], vec[++j]);
- }
- swap(vec[++j], vec[right]);
- if (j == k)
- return;
- if (j > k)
- HoareQuickSort(vec, left, j - 1, k);
- if (j < k)
- HoareQuickSort(vec, j + 1, right, k - j + left - 1);
- }
- }
- // Run-time complexity O(n)
- vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
- vector<Point> distances;
- // O(n)
- for (int i = 0; i < points_set.size(); ++i) {
- int dist = (points_set[i][0] - p[0])*(points_set[i][0] - p[0]) + (points_set[i][1] - p[1])*(points_set[i][1] - p[1]);
- Point np(points_set[i][0], points_set[i][1], dist);
- distances.push_back(np);
- }
- // O(n)
- HoareQuickSort(distances, 0, distances.size() - 1, k);
- vector<vector<int>> ans(k, vector<int> (2));
- // O(k)
- for (int i = 0; i < k; ++i) {
- vector<int> v = {distances[i].x, distances[i].y};
- ans[i] = v;
- }
- return ans;
- }
- void PrintVector(const vector<vector<int>>& points_set) {
- for (int i = 0; i < points_set.size(); ++i) {
- std::cout << "(" << points_set[i][0] << ", " << points_set[i][1] << ")" << std::endl;
- }
- }
- void PrintGrid(const vector<vector<int>>& points_set, const vector<int>& p) {
- int min_x = numeric_limits<int>::max();
- int min_y = numeric_limits<int>::max();
- int max_x = numeric_limits<int>::min();
- int max_y = numeric_limits<int>::min();
- for (vector<int> point : points_set) {
- if (point[0] < min_x)
- min_x = point[0];
- if (point[0] > max_x)
- max_x = point[0];
- if (point[1] > max_y)
- max_y = point[1];
- if (point[1] < min_y)
- min_y = point[1];
- }
- vector<vector<char>> grid(max_x - min_x + 1, vector<char> (max_y - min_y + 1, '-'));
- for (int i = 0; i < grid.size(); ++i) {
- for (int j = 0; j <grid[0].size(); ++j) {
- for (vector<int> point : points_set) {
- if (point[0] == i && point[1] == j)
- grid[i][j] = 'x';
- }
- if (p[0] == i && p[1] == j)
- grid[i][j] = 'o';
- }
- }
- for (int i = 0; i < grid.size(); ++i) {
- for (int j = 0; j < grid[0].size(); ++j) {
- std::cout << grid[i][j] << " ";
- }
- std::cout << std::endl;
- }
- }
- int main()
- {
- srand(time(NULL));
- vector<vector<int>> points_set{{0, 0}, {1, 5}, {3, 9}, {4, 0}, {2, 7}, {3, 2}, {4, 6}, {2, 3}};
- vector<int> p{2, 4};
- int k = 5;
- vector<vector<int>> kpoints_set = KNearestPoints(points_set, p, k);
- PrintGrid(points_set, p);
- PrintVector(kpoints_set);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement