Сортировка массива результатов

Question

Мне задали этот вопрос в интервью Adobe:

У нас есть целочисленный массив, отсортированный по возрастанию. У нас также есть 3 целых числа A, B и C. Нам нужно применить A*x*x + B*x + C для каждого элемента x в массиве и вернуть соответствующий отсортированный массив.

Пример, который мне дали:

Input array = -1 0 1 2 3 4
A = -1, B = 2, C = -1`

Результат применения формулы к каждому элементу = -4 -1 0 -1 -4 -9
Итак, ожидаемый результат = -9 -4 -4 -1 -1 0 (отсортировано)

Моим лучшим решением было применить формулу и отсортировать ее, получив O(nlogn) решение. Я не мог сделать это лучше.

Любое руководство по его улучшению полезно.

Answer 1

Уравнение дано параболическое .Таким образом, результат применения его к отсортированному массиву приведет к массиву, который будет иметь максимум / минимум с отсортированными подмассивами слева и справа.

В вашем случае максимум равен 0 ивложенный массив слева [-4 -1] отсортирован в порядке возрастания, а вспомогательный массив справа [-1 -4 -9] отсортирован в порядке убывания.

Все, что вам нужно сделать, это слияниеэти отсортированные массивы , которые являются линейными по времени.

Таким образом, алгоритм таков:

1. Применить уравнение для каждого элемента
2. Найти максимум / минимум
3. Объединить подмассивы

Answer 2

Вы можете сделать это в O(n). Найти минимальное значение полинома, которое имеет место, когда

2 * A * x + B = 0

так что

x_min = -B / 2 * A.

Затем обойдите массив, пока не найдете целое число, ближайшее к x_min. Это O(n). Отсюда последовательно выбирайте слева или справа от этого элемента в зависимости от того, |x_min - left| меньше или больше, чем |x_min - right|. Вернуть значения оценки полинома в этих точках в результирующем порядке. Это O(n).

Предполагается, что A является положительным. Вы можете обрабатывать случай отрицательного A аналогичным образом.

Пример:

input array = -1 0 1 2 3 4 A = -1, B = 2, C = -1

Здесь максимальное значение достигается при x_max = -2 / 2 * -1 = 1. Из входного массива ближайшим значением является 1, третий элемент. Затем мы последовательно выбираем элементы в следующем порядке, исходя из их расстояния до 1.

1, 0, 2, -1, 3, 4

Тогда, поскольку A отрицательно, мы должны запустить их в обратном порядке

4, 3, -1, 2, 0, 1

и оценим полином по ним

-9, -4, -4, -1, -1, 0

Готово.

Обратите внимание, что мы используем специальное свойство парабол. А именно, для x меньше x_extreme и A положительного, применение многочлена к такому x является убывающей функцией x. Для x больше x_extreme и A положительного, применение полинома к такому x является возрастающей функцией x. (Аналогичные рассуждения применимы, если A отрицательно.) Таким образом, разбейте массив на две части: те, которые x меньше x_extreme и те x больше x_extreme. Затем примените многочлен к этим двум частям, чтобы получить два отсортированных массива. Теперь примените объединение, отсортированное к этим отсортированным массивам. Обратите внимание, что приведенное выше описание является сортировкой слиянием.

Answer 3

Решение - O(N), и нет необходимости выполнять какие-либо исчисления, хотя это помогает понять форму кривой.

Ответы выше делают наиболее интуитивную вещь и решают уравнение длянайдите минимум или максимум и затем разбейте список.

Преимущество в вычислении первой производной есть, но нет необходимости делать это на самом деле, а также нам не нужно находить максимальную или минимальную точку в это время.

Просто знайте, что он может двигаться в одном направлении, а затем назад в другом, но никогда не изменит направление более одного раза.

Мы собираемся начать с каждого конца и повторять по обе стороныпока мы не сольемся где-то посередине.Прежде чем делать что-то еще, нам нужно проверить направление на каждом конце, что мы сделаем, просто сравнив два последних элемента.Итак, мы видим, движется ли один конец вверх, а другой вниз.

Если у нас есть N элементов, скажем, у нас есть данные X[0] и X[N-1], поэтому рассчитайте f(X[0]) и f(X[N-1]) и f(X[1]) и f(X[N-2]).Если f(X[0]) < f(X[1]) и f(X[N-1]) > f(X[N-2]), то фактически все наши данные являются одной стороной от максимума / минимума и, таким образом, уже отсортированы.То же самое, если сравнения в другом направлении.(Для одного направления может потребоваться обратное направление).

В противном случае просто выполните объединение с обоих концов, поэтому f(X[0]) и f(X[N-1]) являются максимумами или минимумами их поддиапазонов (мы знаем из более ранних сравнений)и создайте объединенный список в любом подходящем направлении.

Применение к вашим данным:

-1 0 1 2 3 4
A = -1, B = 2, C = -1`

f = [ -4, -1, 0, -1, -4, -9 ]

-4 < -1 и -9 < -4, поэтому мы пересекаем точку и получаем минимумы накаждый конец.

-9 is lower than -4
-4 and -4 are equal so push both
-1 and -1 are equal so push both
0 remains.

our sequence is [-9, -4, -4, -1, -1, 0 ]

Answer 4

Вы можете распознать, что результат применения квадратичного к данным почти отсортирован (как описано в ответах выше, или узнав, что производная многочлена степени n непрерывна, степени n - 1 и имеет большинство n нулей).

Так что, если в вашей библиотеке есть процедура сортировки, которая делает что-то умное с почти отсортированными данными (например, сортировка слиянием, которая учитывает это), вы можете просто выбросить данные и ожидать линейной производительности. При поиске в Интернете Какой алгоритм сортировки лучше всего работает с отсортированными данными? который указывает на http://svn.python.org/projects/python/trunk/Objects/listsort.txt.