Leetcode 719. Find K-th Smallest Pair Distance

문제

The distance of a pair of integers a and b is defined as the absolute difference between a and b.

Given an integer array nums and an integer k, 
return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.

• 정수 배열 arr과 k가 주어진다.
• 정수간의 거리는 두 정수의 차의 절대값이다.
• index i, j에 대해 i < j 인 두 index에 대한 모든 거리들 중 k번째로 짧은 거리는 무엇인가?

예시

nums 가 [1, 3, 1]일 경우,
모든 거리는 [0, 2, 2] 이다 ( 3 - 1, 1 - 1, 1 - 3 )
1 번째로 짧은 거리 : 0
2 번째로 짧은 거리 : 2
3 번째로 짧은 거리 : 2

제한

• $n == nums.length$
• $2 <= n <= 10^4$
• $0 <= nums[i] <= 10^6$
• $1 <= k <= n * (n-1) / 2$

풀이법

• 이 문제의 정답은 반드시 0 ~ 최대거리 사이에 존재한다.
• 먼저 nums를 오름차순으로 정렬하는것으로 문제 풀이를 시작한다.

이진탐색

• 0 ~ 최대거리 사이에 답이 존재한다는것을 알기에 일단 이 정 중앙 값 mid를 찾아본다.
• 그 후 거리가 0 ~ mid 사이에 존재하는 거리의 수는 정렬된 nums에서 빠르게 구할수 있다.
• 만약 0 ~ mid 인 거리의 갯수가 k와 같거나 많은 경우 -> k번째 값은 반드시! 0 ~ mid 사이에 존재한다는 의미가 된다.
  • 이진탐색의 right 를 mid로 바꾼다.
• 만약 0 ~ mid 인 거리의 갯수가 k보다 작은 경우 -> k번째 값은 반드시! mid 보다 크게 된다.
  • 이진탐색의 left 를 mid + 1 로 바꾼다.
• left 와 right의 값이 같아지면 그 값이 정답이 된다!

코드

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()

		# 0 ~ target 까지의 거리를 가지는 쌍의 갯수를 구한다.
        def count(n: List[int], target: int):
            left = 0
            c = 0

            for right in range(1, len(n)):
            	# right - left의 값이 target보다 크면 left를 증가시킨다.
                while left < right and n[right] - n[left] > target:
                    left += 1
                # 그 사이 가능한 모든 pair의 갯수들.
                c += right - left

            return c

        maxValue = nums[-1] - nums[0]

		# 탐색 공간을 설정한다.
        left = 0
        right = maxValue

        while left != right:
        	# 기준이 될 mid를 구한다.
            mid = (left + right) // 2

            # 0 ~ mid 의 거리를 가지는 모든 pair의 갯수를 구한다.
            midCount = count(nums, mid)

			# 갯수가 k보다 크거나 같을경우 정답은 left ~ mid 사이에 있다는 의미이기에 right 를 mid로
            if midCount >= k:
                # if left ~ mid value can be answer
                right = mid
            # 갯수가 k보다 작을 경우 정답은 mid + 1 ~ right 사이에 있다는 의미이기에 left 를 mid + 1로
            else:
                # if left ~ mid value cannot be answer
                # exclude mid from answer too
                left = mid + 1

        return left