Для массива с отрицательными числами используйте два указателя по краям и заполняйте результат с конца самым большим квадратом. Это O(n) времени и O(n) памяти под ответ.
Дан отсортированный массив чисел. Нужно вернуть отсортированный массив квадратов этих чисел.
Для массива с отрицательными числами используйте два указателя по краям и заполняйте результат с конца самым большим квадратом. Это O(n) времени и O(n) памяти под ответ.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Дан отсортированный массив чисел. Нужно вернуть отсортированный массив квадратов этих чисел.
Пример: Input: nums = [0, 1, 1, 6, 12, 20] Output: squares = [0, 1, 1, 36, 144, 400]
Ответ
Для массива с отрицательными числами используйте два указателя по краям и заполняйте результат с конца самым большим квадратом. Это O(n) времени и O(n) памяти под ответ.
Алгоритм подходит и к приведённому неотрицательному примеру:
def sorted_squares(nums):
result = [0] * len(nums)
left, right = 0, len(nums) - 1
for index in range(len(nums) - 1, -1, -1):
if abs(nums[left]) > abs(nums[right]):
result[index] = nums[left] ** 2
left += 1
else:
result[index] = nums[right] ** 2
right -= 1
return result
Наибольший модуль находится на одном из краёв отсортированного массива. Пустой вход возвращает пустой список. Простое возведение по порядку работает только при подходящем знаковом диапазоне.