JuniorКодЧастоЕщё не отвечали
Отсортированные квадраты отсортированного массива за O(n)
Дан массив целых чисел, упорядоченный по неубыванию (могут быть отрицательные). Верните новый массив квадратов каждого числа, тоже упорядоченный по неубыванию.
Требования:
отрицательный элемент в начале.
- O(n) время — не возводить в квадрат и потом сортировать (это O(n log n)).
- Учесть отрицательные значения: наибольший квадрат может дать самый
std::vector<int> sortedSquares(const std::vector<int>& nums) {
// ваш код здесь
}Допишите реализацию.
Два указателя по обоим концам: наибольший квадрат — на одном из концов, так как вход отсортирован. Сравнивайте abs(nums[left]) и abs(nums[right]), записывайте больший квадрат в результат с конца и двигайте этот указатель внутрь. Один проход, O(n) время и O(n) память.
- ✗Возводить в квадрат и сортировать, теряя оценку O(n), которую даёт метод двух указателей
- ✗Считать квадраты уже отсортированными, раз вход был отсортирован, — неверно при наличии отрицательных
- ✗Заполнять результат с начала, а не с конца, из-за чего большие квадраты попадают не в те ячейки
- →Где именно находится наибольший квадрат до начала прохода и почему?
- →Как изменился бы подход, если бы вход вообще не был отсортирован?
Оглавление
Задача
Дан отсортированный по неубыванию массив (возможны отрицательные). Верните квадраты его элементов в порядке неубывания за O(n).
Решение
#include <vector>
#include <cstdlib>
std::vector<int> sortedSquares(const std::vector<int>& nums) {
int n = static_cast<int>(nums.size());
std::vector<int> result(n);
int left = 0, right = n - 1, pos = n - 1;
while (left <= right) {
int l = nums[left] * nums[left];
int r = nums[right] * nums[right];
if (l > r) { result[pos--] = l; ++left; } // больший квадрат — слева
else { result[pos--] = r; --right; } // больший квадрат — справа
}
return result;
}Ключевые моменты
- Наибольший по модулю элемент стоит на одном из концов, поэтому два указателя сходятся внутрь.
- Результат заполняется с конца — туда кладётся текущий максимальный квадрат.
- Один проход даёт O(n); вариант «квадраты + sort» работает за O(n log n).
Оглавление
