✏️ Задача с собеса: квадраты отсортированного массива

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

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

1. Обрабатываем два края массива (left и right), сравниваем их квадраты.

2. Наибольший квадрат записываем в конец результирующего массива.

3. Сдвигаем соответствующий указатель — либо left, либо right.

4. В конце получаем отсортированный массив квадратов.

Решение с двумя указателями:

public int[] SortedSquares(int[] nums) {
    int n = nums.Length;
    int[] result = new int[n];
    int left = 0, right = n - 1, pos = n - 1;

    while (left <= right) {
        int leftSq = nums[left] * nums[left];
        int rightSq = nums[right] * nums[right];

        if (leftSq > rightSq) {
            result[pos] = leftSq;
            left++;
        } else {
            result[pos] = rightSq;
            right--;
        }
        pos--;
    }
    return result;
}

➡️ Попробовать на литкоде

🐸 Библиотека шарписта

#dotnet_challenge