MiddleКодИногдаЕщё не отвечали
Минимальная абсолютная разность элементов двух массивов
Даны два целочисленных массива a и b. Найдите минимум abs(a[i] - b[j]) по всем парам. Массивы можно сортировать на месте.
Требования:
- Без доп. памяти сверх сортировки; цель — O(n log n), затем линейное слияние.
- Защититесь от переполнения вычитания и пустых массивов.
long long minDistance(std::vector<int>& a, std::vector<int>& b) {
// ваш код здесь
}Допишите реализацию.
Сортируем оба массива, затем идём по ним двумя указателями. На каждом шаге фиксируем abs(a[i] - b[j]) и продвигаем указатель на меньшем значении — сдвиг большего лишь расширил бы разрыв. Минимум на этом слиянии и есть глобальный минимум. Вычитаем в 64 битах, избегая переполнения. O(n log n).
- ✗Продвигать не тот указатель, из-за чего ближайшие пары пропускаются
- ✗Вычитать в 32-битных int и переполняться на крайних значениях
- ✗Не обрабатывать пустой массив, у которого нет допустимой пары
- →Почему продвижение меньшего значения никогда не пропускает оптимум?
- →Как
lower_boundдаст альтернативу O(n log n) без слияния?
Оглавление
Задача
Найдите минимум abs(a[i] - b[j]) по всем парам за O(n log n).
Решение
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdlib>
long long minDistance(std::vector<int>& a, std::vector<int>& b) {
if (a.empty() || b.empty()) return LLONG_MAX; // нет допустимой пары
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
size_t i = 0, j = 0;
long long best = LLONG_MAX;
while (i < a.size() && j < b.size()) {
long long d = std::llabs((long long)a[i] - (long long)b[j]); // 64-бит
best = std::min(best, d);
if (a[i] < b[j]) ++i; else ++j; // двигаем меньший
}
return best;
}Ключевые моменты
- Сортировка обоих + слияние двумя указателями находит ближайшую пару.
- Продвигаем указатель меньшего значения — больший лишь расширил бы разрыв.
- Вычитание в 64 битах спасает от переполнения на
INT_MIN/INT_MAX.
Оглавление
