Сложность: 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-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению.
😎 Решение:
func smallestDistancePair(_ nums: [Int], _ k: Int) -> Int {
let nums = nums.sorted()
func countPairs(_ mid: Int) -> Int {
var count = 0, j = 0
for i in 0..<nums.count {
while j < nums.count && nums[j] - nums[i] <= mid {
j += 1
}
count += j - i - 1
}
return count
}
var left = 0, right = nums.last! - nums.first!
while left < right {
let mid = (left + right) / 2
if countPairs(mid) < k {
left = mid + 1
} else {
right = mid
}
}
return left
}Ставь 👍 и забирай 📚 Базу знаний