Задача: 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⃣Сортировка по цифре
Для каждой цифры (разряда) используем подсчет для сортировки массива.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int[] SortTransformedArray(int[] nums, int a, int b, int c) {
        int[] transformed = nums.Select(x => a * x * x + b * x + c).ToArray();
        RadixSort(transformed);
        return transformed;
    }

    private void RadixSort(int[] array) {
        int maxElement = array.Select(x => Math.Abs(x)).Max();
        int placeValue = 1;

        while (maxElement / placeValue > 0) {
            CountingSortByDigit(array, placeValue);
            placeValue *= 10;
        }

        var negatives = array.Where(x => x < 0).OrderBy(x => x).ToArray();
        var positives = array.Where(x => x >= 0).OrderBy(x => x).ToArray();
        Array.Copy(negatives, 0, array, 0, negatives.Length);
        Array.Copy(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];

        foreach (int num in 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]--;
        }

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

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