JuniorКодЧастоЕщё не отвечали
Два наибольших числа в массиве за один проход
Верните два наибольших значения в массиве целых чисел за один линейный проход. Корректно обрабатывайте отрицательные числа и дубликаты.
Требования:
сообщить об этом).
- O(n) время, O(1) память — без сортировки.
- Решите, что делать при массиве менее чем из двух элементов (например,
std::pair<int,int> twoLargest(const std::vector<int>& a) {
// ваш код здесь
}Допишите реализацию.
Держите две переменные max1 и max2, обе инициализированы наименьшим возможным значением (не 0). Для каждого элемента: если он больше max1, перенесите max1 в max2 и обновите max1; иначе если он больше max2, обновите max2. Ключевое else if не даёт потерять старый максимум. Один проход, O(n).
- ✗Опускать ветку
else if (x > max2), из-за чего второй максимум затирается первым - ✗Инициализировать максимумы нулём, что ломается на полностью отрицательных массивах
- ✗Не обрабатывать массив менее чем из двух элементов
- →Почему инициализация нулём не работает для полностью отрицательного массива?
- →Как обобщить это до K наибольших элементов?
Оглавление
Задача
Верните два наибольших значения за один проход O(n), без сортировки, верно для отрицательных и дубликатов.
Решение
#include <vector>
#include <utility>
#include <climits>
#include <stdexcept>
std::pair<int,int> twoLargest(const std::vector<int>& a) {
if (a.size() < 2) throw std::invalid_argument("need at least 2 elements");
int max1 = INT_MIN, max2 = INT_MIN;
for (int x : a) {
if (x > max1) { max2 = max1; max1 = x; } // новый максимум, старый -> второй
else if (x > max2) { max2 = x; } // обязательная ветка
}
return {max1, max2};
}Ключевые моменты
else if (x > max2)спасает старый максимум — без неё второй максимум теряется.- Инициализация
INT_MIN, а не 0 — иначе полностью отрицательный массив сломается. - Один проход, O(n) время, O(1) память.
Оглавление
