Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

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

👨‍💻 Алгоритм:

1⃣Отсортируйте массив nums.

2⃣Определите минимальное и максимальное возможные расстояния.

3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению.

😎 Решение:

function countPairs($nums, $mid) {
    $count = 0;
    $j = 0;
    for ($i = 0; $i < count($nums); $i++) {
        while ($j < count($nums) && $nums[$j] - $nums[$i] <= $mid) {
            $j++;
        }
        $count += $j - $i - 1;
    }
    return $count;
}

function smallestDistancePair($nums, $k) {
    sort($nums);
    $left = 0;
    $right = $nums[count($nums) - 1] - $nums[0];
    while ($left < $right) {
        $mid = (int)(($left + $right) / 2);
        if (countPairs($nums, $mid) < $k) {
            $left = $mid + 1;
        } else {
            $right = $mid;
        }
    }
    return $left;
}

Ставь 👍 и забирай 📚 Базу знаний