JuniorКодЧастоЕщё не отвечали
Минимальное произведение любой пары элементов массива
Дана последовательность целых чисел. Найдите минимально возможное произведение пары из двух различных элементов (не обязательно соседних).
Требования:
положительное может быть минимумом.
- O(n) время, O(1) память — без сортировки и вложенных циклов.
- Учтите отрицательные: два отрицательных дают положительное; отрицательное на
long long minPairProduct(const std::vector<int>& a) {
// ваш код здесь
}Допишите реализацию.
Отслеживайте два наименьших и два наибольших значения за один проход. Кандидаты на минимум — min1*min2, max1*max2 (два больших отрицательных дают малое произведение) и min1*max1 при смешанных знаках; сравните их и возьмите наименьший. O(n) время, O(1) память; следите за переполнением, используя long long.
- ✗Рассматривать только два наименьших, упуская случай двух больших отрицательных
- ✗Переполнять
intпри умножении двух значений большого модуля - ✗Сортировать (O(n log n)), когда ожидается проход за O(n)
- →Почему два больших отрицательных числа никогда не дают минимальное произведение?
- →Как меняется ответ для максимального произведения?
Оглавление
Задача
Найдите минимальное произведение пары элементов за O(n), учитывая отрицательные и переполнение.
Решение
#include <vector>
#include <climits>
#include <algorithm>
long long minPairProduct(const std::vector<int>& a) {
long long min1 = LLONG_MAX, min2 = LLONG_MAX;
long long max1 = LLONG_MIN, max2 = LLONG_MIN;
for (long long x : a) {
if (x < min1) { min2 = min1; min1 = x; } else if (x < min2) min2 = x;
if (x > max1) { max2 = max1; max1 = x; } else if (x > max2) max2 = x;
}
// кандидаты: два наименьших, два наибольших, крайние
return std::min({min1 * min2, max1 * max2, min1 * max1});
}Ключевые моменты
- Минимум даёт один из трёх кандидатов:
min1*min2,max1*max2,min1*max1. long longзащищает от переполнения при умножении больших значений.- Один проход O(n) против двойного цикла O(n²) или сортировки O(n log n).
Оглавление
