. 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!