Задача: 360. Sort Transformed Array
Сложность: medium

Дан отсортированный массив целых чисел nums и три целых числа a, b и c. Примените квадратичную функцию вида f(x) = ax^2 + bx + c к каждому элементу nums[i] в массиве и верните массив в отсортированном порядке.

Пример:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

👨‍💻 Алгоритм:

1⃣Преобразование и сортировка
Преобразуем каждый элемент массива nums по квадратичной функции f(x) = ax^2 + bx + c и сохраняем результаты в массив transformed. Используем алгоритм поразрядной сортировки для сортировки массива transformed.

2⃣Поразрядная сортировка
Находим максимальное значение по модулю в массиве для определения количества цифр. Применяем поразрядную сортировку к массиву transformed.

3⃣Сортировка по цифре
Для каждой цифры (разряда) используем подсчет для сортировки массива.

😎 Решение:

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] transformed = new int[n];

        for (int i = 0; i < n; ++i) {
            int num = nums[i];
            transformed[i] = a * num * num + b * num + c;
        }

        radixSort(transformed);

        return transformed;
    }

    private void radixSort(int[] array) {
        int maxElement = Math.abs(array[0]);
        for (int num : array) {
            maxElement = Math.max(maxElement, Math.abs(num));
        }

        for (int placeValue = 1; maxElement / placeValue > 0; placeValue *= 10) {
            countingSortByDigit(array, placeValue);
        }

        int[] negatives = Arrays.stream(array).filter(x -> x < 0).toArray();
        int[] positives = Arrays.stream(array).filter(x -> x >= 0).toArray();

        Arrays.sort(negatives);
        Arrays.sort(positives);

        System.arraycopy(negatives, 0, array, 0, negatives.length);
        System.arraycopy(positives, 0, array, negatives.length, positives.length);
    }

    private void countingSortByDigit(int[] array, int placeValue) {
        int n = array.length;
        int[] output = new int[n];
        int[] count = new int[10];

        for (int num : array) {
            int digit = (Math.abs(num) / placeValue) % 10;
            count[digit]++;
        }

        for (int i = 1; i < 10; ++i) {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; --i) {
            int num = array[i];
            int digit = (Math.abs(num) / placeValue) % 10;
            output[count[digit] - 1] = num;
            count[digit]--;
        }

        System.arraycopy(output, 0, array, 0, n);
    }
}

Ставь 👍 и забирай 📚 Базу знаний