719. K번째 최소 쌍 거리 찾기

난이도: 어려움

주제: 배열, 두 포인터, 이진 검색, 정렬

정수 a와 b의 쌍의 거리는 a와 b 사이의 절대 차이로 정의됩니다.

정수 배열 nums와 정수 k가 주어지면 모든 쌍 nums[i] 및 nums[j] 중에서 ^k번째 가장 작은 거리를 반환합니다. 여기서 0 .

예 1:

• 입력: nums = [1,3,1], k = 1
• 출력: 0
• 설명: 모든 쌍은 다음과 같습니다.

  (1,3) -> 2
  (1,1) -> 0
  (3,1) -> 2

그러면 첫 번째^번째 가장 작은 거리 쌍은 (1,1)이고 거리는 0입니다.

예 2:

• 입력: nums = [1,1,1], k = 2
• 출력: 0

예 3:

• 입력: nums = [1,6,1], k = 3
• 출력: 5

제약조건:

• n == 숫자.길이
• 2 4
• 0 6
• 1

힌트:

1. 답변에 대한 이진 검색입니다. 거리

해결책:

이진 검색과 두 포인터 기술을 조합하여 사용할 수 있습니다. 이 문제를 해결하기 위한 단계별 접근 방식은 다음과 같습니다.

접근하다:

1. 배열 정렬: 먼저 배열 번호를 정렬합니다. 정렬은 주어진 값보다 작거나 같은 거리를 가진 쌍의 수를 효율적으로 계산하는 데 도움이 됩니다.

2. 거리에 대한 이진 검색: 이진 검색을 사용하여 k번째로 작은 거리를 찾습니다. 거리에 대한 검색 공간의 범위는 0(가능한 최소 거리)부터 max(nums) - min(nums)(최대 가능한 거리)까지입니다.

3. 거리가 중간 이하인 쌍 계산: 이진 검색의 각 중간 값에 대해 거리가 중간보다 작거나 같은 쌍의 수를 셉니다. 이는 두 포인터 접근 방식을 사용하여 효율적으로 수행할 수 있습니다.

4. 이진 검색 범위 조정: 거리가 중간보다 작거나 같은 쌍의 수에 따라 이진 검색 범위를 조정합니다. 개수가 k보다 작으면 하한을 늘립니다. 그렇지 않으면 상한을 줄입니다.

이 솔루션을 PHP로 구현해 보겠습니다: 719. K번째 최소 쌍 거리 찾기

설명:

• countPairsWithDistanceLessThanOrEqualTo: 이 함수는 거리가 중간보다 작거나 같은 쌍 수를 계산합니다. 두 개의 포인터를 사용합니다. 여기서 right는 현재 요소이고 left는 nums[right]와 nums[left]의 차이가 mid보다 작거나 같을 때까지 조정됩니다.

• smallestDistancePair: 이 함수는 이진 검색을 사용하여 k번째로 작은 거리를 찾습니다. 낮은 값과 높은 값은 거리에 대한 현재 검색 범위를 정의합니다. mid 값은 countPairsWithDistanceLessThanOrEqualTo 함수를 사용하여 확인됩니다. 결과에 따라 검색 공간이 조정됩니다.

이 알고리즘은 O(n log(max(nums) - min(nums)) n log n)의 시간 복잡도로 k번째로 작은 쌍 거리를 효율적으로 찾습니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이와 같이 더 유용한 콘텐츠를 원하시면 언제든지 저를 팔로우하세요.

• 링크드인
• GitHub