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 ;
}
};
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 func smallestDistancePair ( nums [] int , k int ) int {
sort . Ints ( nums )
n := len ( nums )
left , right := 0 , nums [ n - 1 ] - nums [ 0 ]
count := func ( dist int ) int {
cnt := 0
for i , v := range nums {
target := v - dist
left , right := 0 , i
for left < right {
mid := ( left + right ) >> 1
if nums [ mid ] >= target {
right = mid
} else {
left = mid + 1
}
}
cnt += i - left
}
return cnt
}
for left < right {
mid := ( left + right ) >> 1
if count ( mid ) >= k {
right = mid
} else {
left = mid + 1
}
}
return left
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 function smallestDistancePair ( nums : number [], k : number ) : number {
nums . sort (( a , b ) => a - b );
const n = nums . length ;
let left = 0 ,
right = nums [ n - 1 ] - nums [ 0 ];
while ( left < right ) {
let mid = ( left + right ) >> 1 ;
let count = 0 ,
i = 0 ;
for ( let j = 0 ; j < n ; j ++ ) {
// 索引[i, j]距离nums[j]的距离<=mid
while ( nums [ j ] - nums [ i ] > mid ) {
i ++ ;
}
count += j - i ;
}
if ( count >= k ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
return left ;
}
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 /**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
function smallestDistancePair ( nums , k ) {
nums . sort (( a , b ) => a - b );
const n = nums . length ;
let left = 0 ,
right = nums [ n - 1 ] - nums [ 0 ];
while ( left < right ) {
const mid = ( left + right ) >> 1 ;
let count = 0 ,
i = 0 ;
for ( let j = 0 ; j < n ; j ++ ) {
while ( nums [ j ] - nums [ i ] > mid ) {
i ++ ;
}
count += j - i ;
}
if ( count >= k ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
return left ;
}