Find K-th Smallest Pair Distance[H,Array,Two Pointers,Binary Search,Sorting]

https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/?envType=daily-question&envId=2024-08-14

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.

 

Example 1:

Input: nums = [1,3,1], k = 1
Output: 0
Explanation: Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.

Example 2:

Input: nums = [1,1,1], k = 2
Output: 0

Example 3:

Input: nums = [1,6,1], k = 3
Output: 5

 

Constraints:

• n == nums.length
• 2 <= n <= 104
• 0 <= nums[i] <= 106
• 1 <= k <= n * (n - 1) / 2

1.Python

Binary Search를 쓰라는데, 굉장히 Naive한 방법만 생각이 난다. 역시나 시간초과..

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        result = []
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                ans = abs(nums[i]-nums[j])
                result.append(ans)
        result.sort()
        return result[k-1]

 

시간을 더 줄일 수 있는 방법이 있을까..? 그래서 Binary Search를 쓰라고 했구먼

 

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()
        left = 0 # min
        right = nums[-1] - nums[0] #max
        #BST
        while left < right:
            mid = (left+right) // 2
            count = 0
            left_idx = 0
            for right_idx in range(len(nums)):
                while nums[right_idx]-nums[left_idx] > mid :
                    left_idx += 1
                count += right_idx - left_idx
            if count < k:
                left = mid+1
            else:
                right = mid
        return left

 

이건 뭐, 대놓고 답지 코드를 봐도 뭔 소린지 모르겠다.

 

너무나도 복잡한 세상이네

 

아 어려워