Сортировка массива с квадратами чисел

Задача с собеседования Яндекса

Дан отсортированный массив из чисел. Требуется получить отсортированный массив из квадратов этих чисел. Особенность - числа в исходном массиве могут быть отрицательными, поэтому изначальный массив может не отражать итоговую сортировку массива. Массив нельзя модифицировать.

@Test  
fun test() {  
    val result = getSquared(intArrayOf(-10, -4, -3, 1, 2, 4, 5, 8, 12))  
    println("${result.toSet()}")  
}

private fun getSquared(array: IntArray): IntArray {  
    var start = 0  
    var end = array.size - 1  
    val result = IntArray(array.size)  
    var index = end  
  
    while (start <= end) {  
        val numberLeft = array[start].absoluteValue  
        val numberRight = array[end].absoluteValue  
  
        val number = if (numberRight > numberLeft) numberRight else numberLeft  
  
        when {  
            numberRight > numberLeft -> end--  
            else -> start++  
        }  
  
        result[index--] = number.sqr  
    }  
  
    return result  
}  
  
val Int.sqr get() = this * this

Объяснение

Так как у нас массив отсортированный, можно делать проверку на итоговую сортировку с помощью двух указателей пример реализации. Мы будем заполнять итоговый массив с конца, сравнивая элементы массива с двух сторон. Сравнивать мы будем абсолютные числа (с помощью Int.absoluteValue ). Проходим по циклу до тех пор, пока указатели не нашли друг друга.

На каждой итерации мы сравниваем значения "с краев", значение бОльшее мы сохраняем в конец итогового списка, увеличивая или уменьшая соответствующий указатель.