Skip to main content

Priority_queue - Question 4

973 K Closest Points to Origin

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).


Constraints:

1 <= k <= points.length <= 10^4

-10^4 < xi, yi < 10^4


Analysis:

It is quite straightforward to find the K points that have the closest distances to the original point.

Since we need to find the smallest values, the root of the priority_queue (pq) is the largest one for all the elements inside the pq.

Once the size of pq is larger than K, we need to pop out one.


See the code below:

class Solution {
public:
    typedef pair<int, int> pp;
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        vector<vector<int>> res;
        int n = points.size();
        priority_queue<pp> pq;
        for(int i=0; i<n; ++i) {
            int x = points[i][0], y = points[i][1];
            pq.push({x*x + y*y, i});
            if(pq.size() > k) pq.pop();
        }
        while(pq.size()) {
            int id = pq.top().second;
            res.push_back(points[id]);
            pq.pop();
        }
        return res;
    }
};



Upper Layer

Comments

Popular posts from this blog

Trie

Trie is a data structure belonging to n-ary trees, which is designed for some specific questions, such as, prefix of strings. (If you have never known what binary tree is, maybe you can check binary tree first before read more about Trie). The fact that there are only 26 different letters greatly reduce the possible choices for each position. Or to make it clear, for each position, there are 26 different choices. In mathematics, it seems to be very large (height^26 for the full tree), but in reality, it is rare to be a full tree for the set of meaningful strings (needs at least height^26 strings to be a full tree!), since the height or length of English words are less than 10 in most cases. Therefore, it is popular in string matching or related operations. Please be noted that the trie structure is not only limited to strings, the same idea can be extended to other data types, such as integer (then it becomes a binary tree, since for bit, there are only two possible values). In the cod...

Dynamic Programming - Hard Level - Question 1

Dynamic Programming - Hard Level - Question 1  Leetcode 1937  Maximum Number of Points with Cost You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix. To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score. However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score. Return the maximum number of points you can achieve. abs(x) is defined as: x for x >= 0. -x for x < 0. Constraints: m == points.length n == points[r].length 1 <= m, n <= 10^5 1 <= m * n <= 10^5 0 <= points[r][c] <= 10^5 Analysis: Based on the description, we can define dp[i][j] as the maximum number of points wit...