Array
Two Pointers
Binary Search
Sorting
Description
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
Solutions
Solution 1
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def smallestDistancePair ( self , nums : List [ int ], k : int ) -> int :
def count ( dist ):
cnt = 0
for i , b in enumerate ( nums ):
a = b - dist
j = bisect_left ( nums , a , 0 , i )
cnt += i - j
return cnt
nums . sort ()
return bisect_left ( range ( nums [ - 1 ] - nums [ 0 ]), k , key = count )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 class Solution {
public int smallestDistancePair ( int [] nums , int k ) {
Arrays . sort ( nums );
int left = 0 , right = nums [ nums . length - 1 ] - nums [ 0 ] ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
if ( count ( mid , nums ) >= k ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
return left ;
}
private int count ( int dist , int [] nums ) {
int cnt = 0 ;
for ( int i = 0 ; i < nums . length ; ++ i ) {
int left = 0 , right = i ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
int target = nums [ i ] - dist ;
if ( nums [ mid ] >= target ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
cnt += i - left ;
}
return cnt ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
public :
int smallestDistancePair ( vector < int >& nums , int k ) {
sort ( nums . begin (), nums . end ());
int left = 0 , right = nums . back () - nums . front ();
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
if ( count ( mid , k , nums ) >= k )
right = mid ;
else
left = mid + 1 ;
}
return left ;
}
int count ( int dist , int k , vector < int >& nums ) {
int cnt = 0 ;
for ( int i = 0 ; i < nums . size (); ++ i ) {
int target = nums [ i ] - dist ;
int j = lower_bound ( nums . begin (), nums . end (), target ) - nums . begin ();
cnt += i - j ;
}
return cnt ;
}
};