Сложность: 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-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению.
😎 Решение:
public class Solution {
public int SmallestDistancePair(int[] nums, int k) {
Array.Sort(nums);
int left = 0, right = nums[nums.Length - 1] - nums[0];
while (left < right) {
int mid = (left + right) / 2;
if (CountPairs(nums, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private int CountPairs(int[] nums, int mid) {
int count = 0, j = 0;
for (int i = 0; i < nums.Length; i++) {
while (j < nums.Length && nums[j] - nums[i] <= mid) {
j++;
}
count += j - i - 1;
}
return count;
}
}Ставь 👍 и забирай 📚 Базу знаний