Задача: 360. Sort Transformed Array
Дан отсортированный массив целых чисел 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 {
fun sortTransformedArray(nums: IntArray, a: Int, b: Int, c: Int): IntArray {
val transformed = nums.map { a * it * it + b * it + c }.toIntArray()
radixSort(transformed)
return transformed
}
private fun radixSort(array: IntArray) {
val maxElement = array.map { Math.abs(it) }.maxOrNull() ?: 0
var placeValue = 1
while (maxElement / placeValue > 0) {
countingSortByDigit(array, placeValue)
placeValue *= 10
}
val negatives = array.filter { it < 0 }.sorted()
val positives = array.filter { it >= 0 }.sorted()
array.indices.forEach { array[it] = if (it < negatives.size) negatives[it] else positives[it - negatives.size] }
}
private fun countingSortByDigit(array: IntArray, placeValue: Int) {
val output = IntArray(array.size)
val count = IntArray(10)
array.forEach { count[(Math.abs(it) / placeValue) % 10]++ }
for (i in 1 until 10) count[i] += count[i - 1]
for (i in array.indices.reversed()) {
val digit = (Math.abs(array[i]) / placeValue) % 10
output[count[digit] - 1] = array[i]
count[digit]--
}
output.indices.forEach { array[it] = output[it] }
}
}👉Новости 👉База вопросов