Squares of a Sorted Array

Q: Какова временная сложность задачи «Квадраты отсортированного массива»?

Решение с двумя указателями работает за время O(n) : каждое значение возводится в квадрат и помещается один раз. Возведение в квадрат с последующей сортировкой занимает O(n log n) . Для результата в обоих случаях требуется O(n) памяти.

ЛегкоДва указателя Сортировка

+10

Дан массив целых чисел nums, отсортированный в неубывающем порядке. В нём могут быть отрицательные значения. Возведите каждое значение в квадрат и верните квадраты в виде нового массива, также отсортированного в неубывающем порядке.

Функция

sortedSquares(nums: integer-array) → integer-array

numsinteger-array: отсортированный массив целых чисел, отрицательные числа допускаются
Возвращаетinteger-array: квадраты каждого значения, отсортированные в порядке неубывания

Ограничения

1 ≤ nums.length ≤ 4000
-10⁴ ≤ nums[i] ≤ 10⁴
nums отсортирован по неубыванию.

Примеры

Ввод: nums = [-6, -2, 1, 3, 7]
Вывод: [1, 4, 9, 36, 49]
Пояснение: Квадраты в исходном порядке — 36, 4, 1, 9 и 49. Отрицательные значения -6 и -2 дают большие квадраты, поэтому при сортировке 36 перемещается ближе к концу: [1, 4, 9, 36, 49].

Ввод: nums = [-9, -4, -1]
Вывод: [1, 16, 81]
Пояснение: Все значения отрицательные, поэтому квадраты располагаются в обратном порядке: 81, 16, 1 превращаются в [1, 16, 81].

+14 скрытых тестов при отправке

Дополнительный вопрос

Возведение в квадрат и сортировка занимают O(n log n). Сможешь ли ты сделать это за O(n)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Возведение в квадрат сохраняет порядок неотрицательных значений, но меняет порядок отрицательных, поэтому квадраты не отсортированы. Повторная сортировка сработает, но проигнорирует заданный вам порядок. Ключевой факт: наибольший квадрат всегда получается из одного из двух концов nums. Сравните значения на двух концах, поместите больший квадрат в конец результата и двигайтесь к середине.

Возведите в квадрат, затем отсортируйте

Идея

Создай новый массив из квадратов каждого значения, а затем отсортируй его. Квадраты никогда не бывают отрицательными, а сортировка упорядочивает их независимо от того, откуда они взялись.

Для [-6, -2, 1, 3, 7] квадраты равны [36, 4, 1, 9, 49], а после сортировки получаем [1, 4, 9, 36, 49].

Сортировка требует O(n log n). Здесь этого достаточно, но при таком подходе считается, будто входные данные вовсе не упорядочены. Следующий подход использует порядок и требует одного прохода.

Алгоритм

Создай массив с x * x для каждого x в nums.
Отсортируй его в порядке возрастания чисел.
Верни его.

def sortedSquares(nums):
    return sorted(x * x for x in nums)

Два указателя с обоих концов

Идея

Представь квадраты как расстояние от 0, возведённое в квадрат. В отсортированном массиве значения, наиболее удалённые от 0, находятся на двух концах: самое отрицательное — слева, а самое положительное — справа. Поэтому наибольшим будет nums[left]² или nums[right]², но никогда — какое-либо значение между ними.

Оставь left равным 0, а right — n-1, и заполняй результат с последней позиции в обратном порядке. На каждом шаге сравнивай квадраты на двух концах, записывай больший в текущую позицию и сдвигай соответствующий указатель к середине. Между указателями снова остаётся отсортированный массив, поэтому на каждом шаге верно то же самое.

Для [-6, -2, 1, 3, 7]: 49 больше 36 и занимает последнее место. Затем 36 больше 9, 9 больше 4, 4 больше 1, а 1 заполняет позицию 0. Результат — [1, 4, 9, 36, 49]. Каждое значение размещается один раз: время работы — O(n), а результат — единственный дополнительный массив.

Алгоритм

Создай массив результата длины n. Установи left равным 0, а right — n-1.
Пройди по позициям от n-1 до 0.
Сравни nums[left]² и nums[right]².
Запиши больший квадрат в pos и передвинь этот указатель на один шаг к середине.
Верни результат.

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    # the largest square left is always at one of the two ends
    for pos in range(n - 1, -1, -1):
        left_sq = nums[left] * nums[left]
        right_sq = nums[right] * nums[right]
        if left_sq > right_sq:
            result[pos] = left_sq
            left += 1
        else:
            result[pos] = right_sq
            right -= 1
    return result

Ловушки и крайние случаи

Вариант с двумя указателями короткий, но есть несколько деталей, которые могут его испортить.

Заполнять результат с начала. Наименьший квадрат находится там, где значения пересекают 0, а это может быть где угодно посередине. По краям можно определить только наибольший квадрат. Заполняйте с конца.
Сравнивать nums[left] и nums[right], а не их квадраты или абсолютные значения. -6 меньше 3, но его квадрат больше.
Останавливаться, когда left встречается с right. Когда они равны, одно значение всё ещё не размещено; переберите каждую позицию результата или используйте left <= right.
Входные данные, состоящие только из отрицательных или только из положительных чисел. При [-9, -4, -1] всю работу выполняет левый указатель, а при [2, 5, 8] — правый. В обоих случаях результат всё равно должен быть отсортирован.
В JavaScript и TypeScript вызов sort() без компаратора сортирует числа как текст, поэтому [1, 4, 36, 9] превращается в [1, 36, 4, 9]. Передайте (a, b) => a - b.

Частые вопросы4

Какова временная сложность задачи «Квадраты отсортированного массива»?

Решение с двумя указателями работает за время O(n): каждое значение возводится в квадрат и помещается один раз. Возведение в квадрат с последующей сортировкой занимает O(n log n). Для результата в обоих случаях требуется O(n) памяти.

Почему самый большой квадрат получается из одного из двух концов?

Квадрат числа увеличивается с его удалённостью от 0. В отсортированном массиве значение, наиболее удалённое ниже 0, — первое, а значение, наиболее удалённое выше 0, — последнее. Любое значение между ними ближе к 0, чем одно из этих значений, поэтому его квадрат не может быть наибольшим.

Можешь заполнить результат с начала?

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

Является ли задача «Квадраты отсортированного массива» задачей на слияние?

В замаскированном виде — да. Квадраты отрицательных значений образуют один отсортированный список (читайте справа налево), а квадраты неотрицательных значений — другой. Их объединение — это этап слияния в сортировке слиянием, поэтому его можно выполнить за один линейный проход.

Python

def sortedSquares(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

nums = [-6, -2, 1, 3, 7]

Ожидается

[1, 4, 9, 36, 49]