우선순위 대기열을 사용하여 원점에 가장 가까운 K개 지점을 찾습니다.

이 문제에서는 주어진 N개 점 중 2D 평면에서 원점에 가장 가까운 K개 점을 찾습니다.

표준 유클리드 거리 공식을 사용하여 원점과 각 지점 사이의 거리를 계산할 수 있습니다. 그런 다음, 거리가 있는 점을 배열에 저장하고, 거리를 기준으로 배열을 정렬하고, 상위 K개 점을 가져올 수 있습니다.

그러나 우선순위 대기열을 사용하여 원점으로부터의 거리를 기준으로 2D 포인트를 저장할 수도 있습니다. 그 후에 대기열에서 K번 대기열을 제거할 수 있습니다.

문제 설명− 2차원 평면에 N개의 점이 주어졌습니다. 평면의 원점에 가장 가까운 K개 점을 찾아야 합니다.

NOTE - 유클리드 거리를 원점과 평면의 주어진 지점 사이의 거리로 생각하세요.

예

들어가세요

으아아아

출력

으아아아

설명 − 각 점에서 원점까지의 유클리드 거리입니다.

• (2, −2) −> sqrt(8)

• (−5, 1) −> sqrt(26)

• (2, 1) -> sqrt(5)

• (0, 3) −> sqrt(9)

• (6, 0) -> sqrt(36)

• (5, 5) -> sqrt(50)

• (4, 9) -> sqrt(97)

따라서 가장 가까운 4개의 점은 {2,1} {2,−2} {0,3} {−5,1}입니다.

들어가세요

으아아아

출력

으아아아

설명 − 모든 점에서 원점까지의 거리는 동일합니다. 따라서 우리는 어떤 2포인트라도 출력으로 인쇄할 수 있습니다.

들어가세요

으아아아

출력

으아아아

설명− K는 주어진 점과 같습니다. 그러므로 모든 점을 인쇄해야 합니다.

방법 1

이 방법에서는 sort() 메서드를 사용하여 배열을 정렬합니다. 또한 비교기 기능을 사용하여 원점으로부터의 거리를 기준으로 점을 정렬합니다. 그런 다음 정렬된 배열의 첫 번째 K개 요소를 인쇄합니다.

알고리즘

1단계 − sort() 메서드를 사용하여 목록을 정렬하고 distComparator() 함수를 세 번째 매개변수로 전달합니다.

2단계− 주어진 지점의 거리를 비교하기 위해 distComparator() 함수를 정의합니다. 이 함수는 p와 q 쌍을 매개변수로 사용합니다.

2.1단계 − 지점 p에서 원점까지의 거리를 구하여 dist_p에 저장합니다.

2.2단계 − q 지점에서 원점까지의 거리를 dist_q 변수에 저장합니다.

2.3단계 − dist_p가 dist_q보다 작으면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

3단계 - 배열을 반복하고 배열의 첫 번째 K 포인트를 인쇄합니다.

예

으아아아

출력

으아아아

시간 복잡도 - 배열 정렬의 시간 복잡도는 O(NlogN)입니다.

공간 복잡도 - 배열 정렬을 위한 O(N)입니다.

방법 2

이 방법에서는 우선순위 대기열을 사용하여 포인트를 삽입합니다. 또한 비교기 기능과 우선순위 대기열을 사용하여 원점으로부터의 최단 거리를 기준으로 포인트를 저장합니다.

알고리즘

1단계 − 'res_points' 목록을 정의하여 K개의 가장 가까운 지점을 저장합니다.

2단계 - 우선순위 대기열을 정의합니다. 여기서 'pair'는 우선순위 큐를 사용하여 정수 쌍을 저장하는 것을 의미합니다. '벡터>'은 벡터를 사용하여 쌍을 저장하는 것을 의미합니다. 또한 우선순위 큐와 함께 "cmp" 기능을 사용했습니다.

3단계− 원점에 대한 두 점의 유클리드 거리를 비교하는 cmp() 함수를 정의합니다.

3.1단계 - a 지점에서 원점까지의 거리가 b 지점에서 원점까지의 거리보다 큰 것을 기준으로 부울 값을 반환합니다.

4단계 - 배열의 각 요소를 우선순위 대기열에 삽입합니다.

5단계− 대기열에서 첫 번째 K개 요소를 꺼내서 res_points 목록에 저장합니다.

6단계− res_points 포인트 목록을 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 - O(N*logN) N개 요소를 우선순위 대기열에 삽입합니다. 여기서 N은 총 포인트 수입니다.

공간 복잡성 - O(N)으로 우선순위 대기열에 포인트를 저장합니다.

우선순위 큐는 힙 데이터 구조를 사용합니다. 따라서 요소를 삽입하고 삭제하는 데는 O(logN) 시간만 걸립니다. 두 방법 모두 동일한 메모리와 시간이 필요합니다. 그러나 두 번째 방법은 힙 데이터 구조를 사용하므로 더 효율적입니다.

위 내용은 우선순위 대기열을 사용하여 원점에 가장 가까운 K개 지점을 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!