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

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

Вы можете сделать это в 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 

Done.

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

Answer 2

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

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

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

Так алгоритм:

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

Answer 3

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

Итак, если у вас в вашей библиотеке есть процедура сортировки, которая делает что-то умное с почти отсортированными данными (например, слияние, которое помнит об этом), вы можете просто выбросить данные на него и ожидать линейной производительности. Поиск в Интернете находит Which sort algorithm works best on mostly sorted data? , который указывает на http://svn.python.org/projects/python/trunk/Objects/listsort.txt.

Answer 4

Решение 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 ]