Квадраты отсортированного массива

Дан список целых чисел nums, упорядоченный по возрастанию, в нём могут быть отрицательные числа. Напишите функцию sorted_squares(nums), которая возвращает список квадратов, упорядоченный по возрастанию, за один проход (O(n)), без вызова sorted и sort.

Пример: [-5, 0, 3, 7, 10] -> [0, 9, 25, 49, 100].

КАК СПРАШИВАЮТСначала принимают `sorted(x * x for x in nums)`, потом просят улучшить до O(n): два указателя с краёв, заполнение результата с конца.

ПОДСКАЗКА

Наибольший по модулю элемент всегда на одном из концов. Два указателя lo и hi, результат заполняется с конца: сравните abs(nums[lo]) и abs(nums[hi]), запишите квадрат большего и сдвиньте его указатель.

РЕШЕНИЕ И РАЗБОР

Сначала попробуйте сами: на собеседовании подсказки не будет.

После возведения в квадрат отрицательные числа «переворачиваются», поэтому наибольший квадрат всегда на одном из концов исходного массива. Два указателя с концов и заполнение результата с конца: сравниваем модули, записываем больший квадрат в текущую позицию и сдвигаем соответствующий указатель.

Заранее созданный список [0] * n даёт запись по индексу без insert(0, ...), который был бы O(n) на каждом шаге.

def sorted_squares(nums):
    res = [0] * len(nums)
    lo, hi = 0, len(nums) - 1
    pos = len(nums) - 1
    while lo <= hi:
        if abs(nums[lo]) >= abs(nums[hi]):
            res[pos] = nums[lo] * nums[lo]
            lo += 1
        else:
            res[pos] = nums[hi] * nums[hi]
            hi -= 1
        pos -= 1
    return res

ментор разберёт с вами

песочница · Pythonрешено 0 / 1

Ctrl+Enter

ТЕСТЫ

Ввод	Ваш вывод	Ожидаемый вывод
[-5, 0, 3, 7, 10]	—	[0, 9, 25, 49, 100]
[-7, -3, 2, 3, 11]	—	[4, 9, 9, 49, 121]
[]	—	[]
[-4, -2]	—	[4, 16]
скрытый тест 5
скрытый тест 6

решённые задания сохранятся в прогресс после входа

Квадраты отсортированного массива

Пример: [-5, 0, 3, 7, 10] -> [0, 9, 25, 49, 100].

ПОДСКАЗКА

РЕШЕНИЕ И РАЗБОР

Сначала попробуйте сами: на собеседовании подсказки не будет.

Заранее созданный список [0] * n даёт запись по индексу без insert(0, ...), который был бы O(n) на каждом шаге.

def sorted_squares(nums):
    res = [0] * len(nums)
    lo, hi = 0, len(nums) - 1
    pos = len(nums) - 1
    while lo <= hi:
        if abs(nums[lo]) >= abs(nums[hi]):
            res[pos] = nums[lo] * nums[lo]
            lo += 1
        else:
            res[pos] = nums[hi] * nums[hi]
            hi -= 1
        pos -= 1
    return res

ментор разберёт с вами

Ввод

Ваш вывод

Ожидаемый вывод

[-5, 0, 3, 7, 10]

—

[0, 9, 25, 49, 100]

[-7, -3, 2, 3, 11]

—

[4, 9, 9, 49, 121]

[]

—

[]

[-4, -2]

—

[4, 16]

скрытый тест 5

скрытый тест 6