Задача: 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 {
    function sortTransformedArray($nums, $a, $b, $c) {
        $transformed = array_map(function($x) use ($a, $b, $c) {
            return $a * $x * $x + $b * $x + $c;
        }, $nums);

        $this->radixSort($transformed);
        return $transformed;
    }

    private function radixSort(&$array) {
        $maxElement = max(array_map('abs', $array));
        $placeValue = 1;

        while ($maxElement / $placeValue > 0) {
            $this->countingSortByDigit($array, $placeValue);
            $placeValue *= 10;
        }

        $negatives = array_filter($array, function($x) { return $x < 0; });
        $positives = array_filter($array, function($x) { return $x >= 0; });
        sort($negatives);
        sort($positives);
        $array = array_merge($negatives, $positives);
    }

    private function countingSortByDigit(&$array, $placeValue) {
        $n = count($array);
        $output = array_fill(0, $n, 0);
        $count = array_fill(0, 10, 0);

        foreach ($array as $num) {
            $digit = (int)(abs($num) / $placeValue) % 10;
            $count[$digit]++;
        }

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

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

        for ($i = 0; $i < $n; $i++) {
            $array[$i] = $output[$i];
        }
    }
}

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