MiddleКодИногдаЕщё не отвечали
K элементов, ближайших к значению x, в отсортированном массиве
Дан отсортированный массив arr, целое k и значение x. Верните k элементов, ближайших к x, по возрастанию. При равенстве предпочитайте меньшее значение.
Требования:
- O(log n + k): бинпоиск точки вставки, затем расширение окна двумя указателями.
std::vector<int> findClosestElements(const std::vector<int>& arr, int k, int x) {
// ваш код здесь
}Допишите реализацию.
Бинпоиском найдите позицию x, затем растите окно размера k. На каждом шаге сравнивайте расстояния границ до x; если x - arr[left-1] <= arr[right] - x, двигайте левую, иначе правую. Знак <= отдаёт ничью меньшему значению. Окно остаётся отсортированным. O(log n + k).
- ✗Возвращать
kэлементов лишь справа от x вместо ближайших с обеих сторон - ✗Использовать
<вместо<=и ломать правило ничьей в пользу меньшего - ✗Допускать выход указателей left/right за границы массива
- →Чем это отличается от поиска k ближайших к a[index], а не к свободному значению x?
- →Почему окно остаётся непрерывным на всём протяжении?
Оглавление
Задача
Верните k элементов отсортированного массива, ближайших к значению x, за O(log n + k).
Решение
#include <vector>
#include <algorithm>
std::vector<int> findClosestElements(const std::vector<int>& arr, int k, int x) {
int left = std::lower_bound(arr.begin(), arr.end(), x) - arr.begin();
int right = left;
while (right - left < k) {
if (left == 0) ++right;
else if (right == (int)arr.size()) --left;
else if (x - arr[left-1] <= arr[right] - x) --left; // ничья -> меньшее
else ++right;
}
return std::vector<int>(arr.begin() + left, arr.begin() + right);
}Ключевые моменты
- Бинпоиск даёт стартовую точку, окно расширяется к ближней стороне.
<=отдаёт ничью меньшему значению.- Окно всегда непрерывно, поэтому результат уже отсортирован.
Оглавление
