360. Sort Transformed Array

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];
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& SortTransformedArray(vector<int>& nums, int a, int b, int c) {
        vector<int>& transformed = nums.Select(x => a * x * x + b * x + c).ToArray();
        RadixSort(transformed);
        return transformed;
    }
    private void RadixSort(vector<int>& array) {
        int maxElement = array.Select(x => 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.size());
        Array.Copy(positives, 0, array, negatives.size(), positives.size());
    }
    private void CountingSortByDigit(vector<int>& array, int placeValue) {
        int n = array.size();
        vector<int>& output = new int[n];
        vector<int>& count = new int[10];
        foreach (int num in array) {
            int digit = (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 = (abs(num) / placeValue) % 10;
            output[count[digit] - 1] = num;
            count[digit]--;
        }
        for (int i = 0; i < n; i++) {
            array[i] = output[i];
        }
    }
}

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);
    }
}

class Solution {
    sortTransformedArray(nums, a, b, c) {
        const transformed = nums.map(x => a * x * x + b * x + c);
        this.radixSort(transformed);
        return transformed;
    }

    radixSort(array) {
        const maxElement = Math.max(...array.map(x => Math.abs(x)));
        let placeValue = 1;

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

        const negatives = array.filter(x => x < 0).sort((a, b) => a - b);
        const positives = array.filter(x => x >= 0).sort((a, b) => a - b);
        array.splice(0, array.length, ...negatives, ...positives);
    }

    countingSortByDigit(array, placeValue) {
        const output = new Array(array.length);
        const count = new Array(10).fill(0);

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

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

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

        array.splice(0, array.length, ...output);
    }
}

class Solution:
    def sortTransformedArray(self, nums, a, b, c):
        transformed = [a * x * x + b * x + c for x in nums]
        self.radix_sort(transformed)
        return transformed

    def radix_sort(self, array):
        max_element = max(abs(num) for num in array)
        place_value = 1

        while max_element // place_value > 0:
            self.counting_sort_by_digit(array, place_value)
            place_value *= 10

        negatives = sorted([x for x in array if x < 0])
        positives = sorted([x for x in array if x >= 0])
        array[:] = negatives + positives

    def counting_sort_by_digit(self, array, place_value):
        output = [0] * len(array)
        count = [0] * 10

        for num in array:
            digit = (abs(num) // place_value) % 10
            count[digit] += 1

        for i in range(1, 10):
            count[i] += count[i - 1]

        for num in reversed(array):
            digit = (abs(num) // place_value) % 10
            output[count[digit] - 1] = num
            count[digit] -= 1

        array[:] = output

package main

import (
    "sort"
    "math"
)

func sortTransformedArray(nums []int, a int, b int, c int) []int {
    transformed := make([]int, len(nums))
    for i, x := range nums {
        transformed[i] = a*x*x + b*x + c
    }

    radixSort(transformed)
    return transformed
}

func radixSort(array []int) {
    maxElement := int(math.Abs(float64(array[0])))
    for _, num := range array {
        maxElement = int(math.Max(float64(maxElement), math.Abs(float64(num))))
    }

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

    negatives := []int{}
    positives := []int{}
    for _, num := range array {
        if num < 0 {
            negatives = append(negatives, num)
        } else {
            positives = append(positives, num)
        }
    }

    sort.Ints(negatives)
    sort.Ints(positives)
    array = append(negatives, positives...)
}

func countingSortByDigit(array []int, placeValue int) {
    n := len(array)
    output := make([]int, n)
    count := make([]int, 10)

    for _, num := range array {
        digit := (int(math.Abs(float64(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(math.Abs(float64(num))) / placeValue) % 10
        output[count[digit]-1] = num
        count[digit]--
    }

    copy(array, output)
}

Explanation

Algorithm

Преобразование и сортировка

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

Поразрядная сортировка

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

Сортировка по цифре

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

😎