K Origin Leetcode 솔루션에 가장 가까운 지점

난이도 중급
자주 묻는 질문 아마존 아사 Facebook 구글 링크드인 Microsoft
배열 분열과 정복 기하학 더미 수학 정렬 서모로직 Tik의 톡조회수 56

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

또한 K Origin LeetCode 솔루션에 가장 가까운 지점 – "원점에 대한 K 가장 가까운 점"은 점 배열이 주어지면 x 좌표와 y 좌표가 XY 평면의 좌표를 나타냄을 나타냅니다. 원점에 가장 가까운 k개의 점을 찾아야 합니다.

두 점 사이의 거리는 두 점 사이의 유클리드 거리와 같습니다.

예:

K Origin Leetcode 솔루션에 가장 가까운 지점

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)입니다.

접근

아이디어 :

  1. 이 문제를 해결하기 위한 주요 아이디어는 우선 순위 대기열.
  2. 모든 좌표에 대해 원점에서 현재 점의 유클리드 거리를 계산합니다.
  3. 좌표와 함께 거리를 푸시하십시오. 우선순위 큐(최대 힙).
  4. 우선순위 큐의 크기가 초과 k 값을 사용하면 원점에서 최대 유클리드 거리를 가진 좌표를 표시해야 하며 해당 좌표는 다음 위치에 표시됩니다. 상단 우선순위 큐의
  5. 마지막으로 우선 순위 대기열에 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.

균열 시스템 설계 인터뷰
Translate »