Рассмотрите элемент массива X является одним из лидеров массива, если все элементы, следующие за этим элементом массива, меньше или равны элементу массива X ... тогда какой лучший алгоритм найти все лидеры массива?лидер массива
Массив может иметь больше лидеров .. Рассмотрим следующий массив [10 9 8 6], а затем 10,9,8 лидеры массива
Работа с правого конца массива, отслеживающих максимальное значение, с которым вы столкнулись. Каждый раз, когда максимум увеличивается или равен, этот элемент является лидером по вашему определению. Более того, он остается лидером, независимо от того, что происходит дальше влево - другими словами, каждый лидер, которого вы добавляете в свой список, является подлинным лидером, а не только кандидатом, так как вы будете работать слева направо.
но он хочет найти всех * лидеров. –
Да, и этот метод делает именно это! –
так верно. Прости. upvoted! –
Ведение списка возможных лидеров при работе с массивом/списком. Этот список, естественно, отсортирован по убыванию. Каждый новый элемент является новым лидером. Если его больше, чем последний найденный возможный лидер, тогда вам нужно устранить всех лидеров, меньших, чем этот новый возможный лидер, и добавить его к теперь усеченному списку. В противном случае просто добавьте его в список возможных лидеров.
Python:
def findleaders(array):
leaders = []
for element in array:
if element < leaders[-1]:
# new possible leader
leaders.append(element)
else:
# remove false possible leaders
while leaders[-1] < element:
leaders.pop()
if not leaders: break #stop when list is empty
leaders.append(element)
return leaders
В Haskell это будет выглядеть как
leaders [] = [];
leaders (a:as)
| all (a>) as = a : leaders as
| otherwise = leaders as
давая список лидеров списка.
Его следует легко адаптировать к массивам.
Этот алгоритм O (n^2), если я правильно его понимаю. См. Ответ Дэвида М для простого алгоритма O (n). –
Да, конечно, ответ Дэвида оптимален для структур данных, которые вы можете пройти назад. Мое algo можно было бы увеличить, сбросив все элементы (
Выведение из алгоритма Дэвида M в
int max = a[LAST_INDEX]
for(int i = a[LAST_INDEX-1] ; i >=0 ; i--) {
if(a[i] > max)
{
printf("%d",a[i]);
max = a[i];
}
}
алгоритм для решения этой проблемы:
Пуск с правой держа дорожки наибольшего элемента (currentLeader). Если найден более крупный элемент, затем распечатайте его и установите currentLeader на текущий элемент. Мы можем считать, что последний элемент является лидером, поскольку справа от него нет элемента.
Можете ли вы объяснить это немного более подробно? Из того, что я могу извлечь из вашего вопроса, в массиве возможен только один «лидер», но ваши вопросы указывают на другое !? –
Нет, рассмотрим этот список: 8 4 7 3 5. И 8 и 7 являются лидерами по этому определению - число после них больше, чем у них. –
@ Давид М: Ты прав! Спасибо, что просветил меня! –