https://leetcode.com/problems/k-closest-points-to-origin/description/
2차원의 정점 정보가 주어질 때 원점에서 k 번째까지 가까운 점들을 찾아라.
priory queue를 구성할 줄 안다면 어렵지 않은 문제.
거리, index의 pair data로 queue를 구성해야 한다.
다만 여기서 거리는 크기의 비교로만 쓰이므로, root 연산은 해지 않아도 된다.(정확할 필요가 없다)
코드
더보기
vector<vector<int>> kClosest(vector<vector<int>>& points, int k)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int q = 0; q < points.size(); ++q)
{
int dist = points[q][0] * points[q][0] + points[q][1] * points[q][1];
pq.push(make_pair(dist, q));
}
vector<vector<int>> vRet;
for (int q = k; q > 0; --q)
{
int idx = (pq.top()).second;
pq.pop();
vRet.push_back(vector<int>{ points[idx][0], points[idx][1] });
}
return vRet;
}
결과
'Leetcode > NeetCode' 카테고리의 다른 글
[PriorityQueue][Medium] 621. Task Scheduler. (3) | 2024.07.20 |
---|---|
[PriorityQueue][Medium] 215. Kth Largest Element in an Array (1) | 2024.07.20 |
[PriorityQueue][Easy] 1046. Last Stone Weight (0) | 2024.07.20 |
[👍][PriorityQueue][Easy] 703. Kth Largest Element in a Stream (0) | 2024.07.19 |
[BinaryTree][Medium] 105. Construct Binary Tree from Preorder and Inorder Traversal (0) | 2024.07.19 |