719. Найдите K-е наименьшее парное расстояние

Сложность: Сложная

Темы: Массив, Два указателя, Двоичный поиск, Сортировка

Расстояние пары целых чисел a и b определяется как абсолютная разница между a и b.

Для заданного целочисленного массива nums и целого числа k верните k^th наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 .

Пример 1:

• Ввод: nums = [1,3,1], k = 1
• Вывод: 0
• Пояснение: Вот все пары:

  (1,3) -> 2
  (1,1) -> 0
  (3,1) -> 2

Тогда первая^-я пара наименьших расстояний равна (1,1), а ее расстояние равно 0.

Пример 2:

• Ввод: nums = [1,1,1], k = 2
• Вывод: 0

Пример 3:

• Ввод: nums = [1,6,1], k = 3
• Выход: 5

Ограничения:

• n == nums.length
• 2 4
• 0 6
• 1

Намекать:

1. Бинарный поиск ответа. Как вы можете проверить, сколько пар имеют расстояние

Решение:

Мы можем использовать комбинацию бинарного поиска и метода двух указателей. Вот пошаговый подход к решению этой проблемы:

Подход:

1. Сортировка массива: сначала отсортируйте числа массива. Сортировка помогает эффективно вычислить количество пар с расстоянием, меньшим или равным заданному значению.

2. Двоичный поиск по расстоянию: используйте бинарный поиск, чтобы найти k-е наименьшее расстояние. Пространство поиска расстояний варьируется от 0 (наименьшее возможное расстояние) до max(nums) - min(nums) (максимально возможное расстояние).

3. Подсчитайте пары с расстоянием ≤ Mid: для каждого среднего значения в двоичном поиске подсчитайте количество пар с расстоянием меньше или равным середине. Это можно эффективно сделать, используя двухточечный подход.

4. Настройка диапазона двоичного поиска: в зависимости от количества пар с расстоянием, меньшим или равным середине, настройте диапазон двоичного поиска. Если счетчик меньше k, увеличьте нижнюю границу; в противном случае уменьшите верхнюю границу.

Давайте реализуем это решение на PHP: 719. Найдите K-е наименьшее парное расстояние

Объяснение:

• countPairsWithDistanceLessThanOrEqualTo: эта функция подсчитывает, сколько пар имеют расстояние меньше или равное середине. Он использует два указателя, где правый — текущий элемент, а левый — корректируется до тех пор, пока разница между nums[right] и nums[left] не станет меньше или равна середине.

• smallestDistancePair: эта функция использует двоичный поиск для поиска k-го наименьшего расстояния. Низкое и высокое значения определяют текущий диапазон поиска расстояний. Среднее значение проверяется с помощью функции countPairsWithDistanceLessThanOrEqualTo. В зависимости от результата пространство поиска корректируется.

Этот алгоритм эффективно находит k-е наименьшее парное расстояние с временной сложностью O(n log(max(nums) - min(nums)) n log n).

Контактные ссылки

Если эта серия оказалась для вас полезной, поставьте звездочку репозиторию на GitHub или поделитесь публикацией в своих любимых социальных сетях? Ваша поддержка очень много значит для меня!

Если вы хотите больше такого полезного контента, подписывайтесь на меня:

• LinkedIn
• GitHub