MiddleКодИногдаЕщё не отвечали
K ближайших по значению к a[index] в отсортированном массиве
Дан неубывающий массив a, индекс index и число k. Верните любые k элементов, значения которых ближе всего к a[index].
Требования:
- O(k) времени двумя указателями, расширяющимися наружу от
index. - Обработайте выход за любой край и массив из одного элемента.
std::vector<int> findKClosest(const std::vector<int>& a, size_t index, size_t k) {
// ваш код здесь
}Допишите реализацию.
Поставьте два указателя на index-1 и index+1, сначала взяв сам a[index]. На каждом шаге сравнивайте расстояния левого и правого кандидатов до a[index] и берите ближнюю сторону, пока не наберёте k. Защитите оба края. O(k), ведь массив отсортирован.
- ✗Выход за левый или правый край без проверки границ
- ✗Неверная обработка массива из одного элемента, где ни один указатель не валиден
- ✗Выбор дальнего из двух равноудалённых кандидатов при заданном правиле разрешения ничьей
- →Чем это отличается от поиска k ближайших к произвольному значению x, а не a[index]?
- →Как сделать разрешение ничьей детерминированным в пользу меньших значений?
Оглавление
Задача
Верните k элементов отсортированного массива, ближайших по значению к a[index], за O(k).
Решение
#include <vector>
#include <cstdlib>
std::vector<int> findKClosest(const std::vector<int>& a, size_t index, size_t k) {
std::vector<int> result;
if (a.empty() || k == 0) return result;
long long pivot = a[index];
long long left = static_cast<long long>(index) - 1, right = index + 1;
result.push_back(a[index]);
while (result.size() < k) {
bool takeLeft;
if (left < 0) takeLeft = false;
else if (right >= (long long)a.size()) takeLeft = true;
else takeLeft = std::llabs(pivot - a[left]) <= std::llabs(a[right] - pivot);
if (left < 0 && right >= (long long)a.size()) break;
if (takeLeft) result.push_back(a[left--]);
else result.push_back(a[right++]);
}
return result;
}Ключевые моменты
- Два указателя расходятся от
index, выбирая ближнего соседа. - Сортировка даёт O(k): расширяемся лишь
kраз. - Проверка обоих краёв и массива из одного элемента обязательна.
Оглавление
