. K번째 최소 쌍 거리 찾기

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

난이도:어려움

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

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

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

예 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 <= 숫자[i] <= 106

1 



힌트:


답을 이진 검색합니다. 거리가 <= X인 쌍이 몇 개인지 어떻게 확인할 수 있나요?


해결책:

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


  
  
  접근하다:



배열 정렬: 먼저 배열 num을 정렬합니다. 정렬은 주어진 값보다 작거나 같은 거리를 가진 쌍의 수를 효율적으로 계산하는 데 도움이 됩니다.
거리에 대한 이진 검색: 이진 검색을 사용하여 k번째로 작은 거리를 찾습니다. 거리에 대한 검색 공간의 범위는 0(가능한 최소 거리)부터 max(nums) - min(nums)(최대 가능한 거리)까지입니다.
거리가 중간인 쌍 계산: 이진 검색의 각 중간 값에 대해 거리가 중간보다 작거나 같은 쌍의 수를 셉니다. 이는 2점 접근 방식을 사용하여 효율적으로 수행할 수 있습니다.
이진 검색 범위 조정: 거리가 중간 이하인 쌍의 수에 따라 이진 검색 범위를 조정합니다. 개수가 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에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 . K번째 최소 쌍 거리 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!