Алгоритм сортировки - найдите, какая панель диаграммы видит другую строку

Мне трудно найти алгоритм с эффективностью runtine O (n).

Если массив имеет размер n, массив содержит целые числа, например.  Я должен знать, какая ячейка массива (может себе представить, как панель диаграммы) смотрит на ячейку.

Формально: lookingAtIndex(i) = max { -1} U {j | arr[j] > arr[i], j<i}< code="">, где <code>-1 обозначает ось y.

<p> <span> Изменить</span>. Каков первый бар, который выше, чем текущий бар, где im at. Если его нет, то его ось Y Пример, снабженный массивом: 7,3,5,2,1,9..</p> <p>Затем 7 смотрит на ось y, 3 смотрит на 7, 5 смотрит на 7, 2 на 5, 1 на 2 и 9 по оси y.</p> <p>Я немного потерян, все, что я делаю, остаюсь в O (nLogn). Это не полный алгоритм сортировки, поэтому можно сделать это с помощью O (n). Печать результатов во время работы, отсутствие необходимости хранить информацию до конца.</p>
3 ответа

Вы можете сделать это с помощью простого стека.

Compare each element a[i] with the top of the stack T
while ( T <= a[i] ) 
 pop T
if the stack is empty
 a[i] is looking at the y-axis
else
 a[i] is looking at T
push a[i] onto the stack

Например, используя массив [7,3,5,2,1,9]

a[0]=7 T=empty 7 is looking at y-axis
a[1]=3 T=7 3 is looking at 7
a[2]=5 T=3 pop 3
 T=7 5 is looking at 7
a[3]=2 T=5 2 is looking at 5
a[4]=1 T=2 1 is looking at 2
a[5]=9 T=1 pop 1
 T=2 pop 2
 T=5 pop 5
 T=7 pop 7
 T=empty 9 is looking at y-axis

Обратите внимание, что каждое число попадает в стек, и каждый номер может быть выведен только один раз из стека, поэтому количество операций стека не превышает 2N, а весь алгоритм O (n).


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

Вот что. Позвольте вызвать входной массив целых чисел I, длины n. Пусть be M наибольшее число в I, найденное в O(n). Сначала я предполагаю, что значение min в I равно 0; если нет, то вычитание значения min не изменяет решение, а M - в общем случае max(I)-min(I).

Создайте массив T длины M, со всеми элементами, установленными в -1. Этот массив является хранилищем индексов столбца "look at" для каждого возможного целого числа в I; инициализация -1, индекс виртуального левого бара.

Создайте также массив S, являющийся выходным массивом o индексов "смотренных" баров.

Теперь, для каждого элемента e в I с индексом I в массиве, он смотрит на панель, индекс которой точно T[e]. Итак, S[i] = T[e]. Затем установите все элементы T[0..e] со значением I.

В конце цикла S заполняется индексами "смотренных" баров; легко вернуть значение этих баров.

Как вы можете видеть, общая сложность O(M*n), поэтому сложность линейна с длиной I. Это может быть не очень эффективно из-за фактора M, как я сказал ранее (любое улучшение приветствуется).

ИЗМЕНИТЬ

Предпочитаете решение user3386109, мое сравнение выглядит неудобно.


Скажем, у нас есть массив, который заканчивается:... A - B,

и lookAtIndex (A) = X, и найдем результат для B:  если A > B, то A, иначе все индексы между A и lookAtIndex (A) не могут быть хорошим ответом, поскольку они меньше A,  если lookAtIndex (A) > B, тогда это ответ, иначе посмотрите на lookAtIndex (lookAtIndex (A)) и т.д.

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

licensed under cc by-sa 3.0 with attribution.