лидер массива

Question

Рассмотрим элемент массива X, который является одним из лидеров массива, если все элементы, следующие за этим элементом массива, меньше или равны элементу массива X ... тогда какой алгоритм лучше всего найти всех лидеров массив

Массив может иметь больше лидеров .. рассмотрите следующий массив [10 9 8 6], тогда 10,9,8 являются лидерами массива

Answer 1

Работа с правого конца массива, отслеживание максимального значения, с которым вы столкнулись. Каждый раз, когда этот максимум увеличивается или равняется, этот элемент является лидером по вашему определению. Более того, он остается лидером независимо от того, что происходит дальше слева - иными словами, каждый лидер, которого вы добавляете в свой список, является настоящим лидером, а не просто кандидатом, как если бы вы работали слева направо.

Answer 2

Алгоритм решения задачи:

Начните с правого отслеживания самого большого элемента (currentLeader). Если найден элемент большего размера, распечатайте его и установите currentLeader в текущий элемент. Мы можем считать, что последний элемент является лидером, поскольку справа от него нет элемента.

https://www.tuturself.com/posts/view?menuId=82&postId=943

Answer 3

Извлечение из алгоритма Дэвида М

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];
 }
}  

Answer 4

В Хаскеле это будет выглядеть как

 leaders [] = [];

leaders (a:as)
          | all (a>) as = a : leaders as
          | otherwise   = leaders as

выдача списка лидеров списка.

• Список лидеров пустого списка пуст
• Если первый элемент списка является лидером, то это также первый элемент списка лидеров.

Должно быть легко адаптироваться к массивам.

Answer 5

Поддерживайте список возможных лидеров, когда вы работаете с массивом / списком. Этот список естественно отсортирован по убыванию. Каждый новый элемент - это возможный новый лидер. Если он больше, чем последний найденный возможный лидер, то вы должны исключить всех лидеров, меньших, чем этот новый возможный лидер, и добавить его в сокращенный список. В противном случае просто добавьте его в список возможных лидеров.

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