시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
또한 K Origin LeetCode 솔루션에 가장 가까운 지점 – "원점에 대한 K 가장 가까운 점"은 점 배열이 주어지면 x 좌표와 y 좌표가 XY 평면의 좌표를 나타냄을 나타냅니다. 원점에 가장 가까운 k개의 점을 찾아야 합니다.
두 점 사이의 거리는 두 점 사이의 유클리드 거리와 같습니다.
예:
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
설명 :
- (1,3)의 거리가 sqrt(10) 단위인 반면 (-2,2)의 거리가 sqrt(8) 단위입니다.
- 최소 거리를 갖는 1점만 반환해야 하므로 (-2,2)가 필요한 답입니다.
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
설명 :
- 원점에서 (3,3)까지의 거리는 sqrt(18) 단위, 원점에서 (5,-1)까지의 거리는 sqrt(26) 단위, 원점에서 (-2,4)까지의 거리는 sqrt(20) ) 단위.
- 따라서 우리의 답은 (3,3)과 (-2,4)입니다.
접근
아이디어 :
- 이 문제를 해결하기 위한 주요 아이디어는 우선 순위 대기열.
- 모든 좌표에 대해 원점에서 현재 점의 유클리드 거리를 계산합니다.
- 좌표와 함께 거리를 푸시하십시오. 우선순위 큐(최대 힙).
- 우선순위 큐의 크기가 초과 k 값을 사용하면 원점에서 최대 유클리드 거리를 가진 좌표를 표시해야 하며 해당 좌표는 다음 위치에 표시됩니다. 상단 우선순위 큐의
- 마지막으로 우선 순위 대기열에 k개의 가장 가까운 지점이 남습니다.
암호
K Origin Leetcode C++ 솔루션에 가장 가까운 지점:
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
priority_queue<vector<int>> q;
for(auto& point:points){
int x = point[0],y = point[1];
int d = x*x + y*y;
q.push({d,x,y});
if(q.size()>k){
q.pop();
}
}
vector<vector<int>> ans;
while(!q.empty()){
ans.push_back({q.top()[1],q.top()[2]});
q.pop();
}
return ans;
}
};
K 출처 Leetcode Java 솔루션에 대한 가장 가까운 지점:
class Solution {
public int[][] kClosest(int[][] points, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((point1, point2) -> point2[0] * point2[0] + point2[1] * point2[1] - point1[0] * point1[0] - point1[1] * point1[1]);
for (int[] point : points) {
pq.offer(point);
if (pq.size() > k) {
pq.poll();
}
}
int[][] ans = new int[k][2];
while (k > 0) {
ans[--k] = pq.poll();
}
return ans;
}
}
원점 Leetcode 솔루션에 대한 K 가장 가까운 점에 대한 복잡성 분석
시간 복잡성
위 코드의 시간 복잡성은 O(NlogK) 전체 입력 배열을 한 번 순회하고 각 포인트는 최대 힙(크기 k)으로 한 번 푸시되기 때문에 N = 입력 배열의 크기이고 K = 최대 힙의 크기입니다.
공간 복잡성
위 코드의 공간 복잡성은 다음과 같습니다. 확인) 우리가 유지하고 있기 때문에 최대 힙 최대 크기 k.
