Найти последнее меньшее или равное число для каждого элемента в массиве?

Мне дали массив. Мне нужно найти последнее (крайнее правое) меньшее или равное число для каждого элемента в массиве.

Например:

2 5 1 6 4 7

2 имеет последний меньший или равный номер 1,
5 имеет последний меньший или равный номер 4, а не 1 и т. д.

Другой пример:

5 100 8 7 6 5 4 3 2 1

Здесь каждый элемент имеет последний меньший или равный номер 1. Я знаю наивный подход, то есть O (n²), но мне нужен лучший подход.

Пожалуйста, объясните логику «последнего минимума», как вы пришли к 1 как «последнему минимуму» для 2?

Lasse V. Karlsen 10.08.2018 09:03

@ LasseVågsætherKarlsen, для элемента мы проверяем все те элементы справа, которые меньше, и выбираем последний меньшего размера.

Watson 10.08.2018 09:05

Я думаю, он имел в виду, что для каждого числа ему нужно найти в оставшемся массиве число, которое меньше текущего, и последнее такое число является последним минимумом.

saketk21 10.08.2018 09:06

Я предполагаю, что последний минимум не существует для наименьшего числа, например, для 1 не будет последнего минимума

Ishpreet 10.08.2018 09:06

@Ishpreet, для 1 можно просто 1.

Watson 10.08.2018 09:08

Можете ли вы объяснить, какой будет наименьший минимум в случае неуникального списка, например, для 2 4 2 3 4, какой будет наименьший минимум для 2?

Ishpreet 10.08.2018 09:08

@Ishpreet, Начиная с последнего, у нас есть последний минимум в индексе 2, если массив имеет 0-индекс.

Watson 10.08.2018 09:11

Какой должен быть ответ? Другой массив?

MBo 10.08.2018 09:25
Структурированный массив Numpy
Структурированный массив Numpy
Однако в реальных проектах я чаще всего имею дело со списками, состоящими из нескольких типов данных. Как мы можем использовать массивы numpy, чтобы...
T - 1Bits: Генерация последовательного массива
T - 1Bits: Генерация последовательного массива
По мере того, как мы пишем все больше кода, мы привыкаем к определенным способам действий. То тут, то там мы находим код, который заставляет нас...
Что такое деструктуризация массива в JavaScript?
Что такое деструктуризация массива в JavaScript?
Деструктуризация позволяет распаковывать значения из массивов и добавлять их в отдельные переменные.
0
8
299
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы могли пойти справа налево и построить минимальный массив из минимального числа до сих пор. Для вашего примера 2 5 1 6 4 7 это будет: Начните с крайнего правого положения:

7
4 7    (4 < 7)
4 4 7  (6 > 4)
...

Итак, минимальный массив для вашего примера будет: 1 1 1 4 4 7

Теперь для каждого запроса вы начинаете с той же позиции в массиве min и идете вправо, пока не найдете число, которое больше:

Для 2:

2 5 1 6 4 7
1 1 1 4 4 7
^
------^

Первый элемент больше 2 равен 4, поэтому верните число непосредственно перед = 1

Для 5:

2 5 1 6 4 7
1 1 1 4 4 7
  ^
----------^

Первый элемент больше 5 равен 7, поэтому верните число непосредственно перед = 4

Чтобы эффективно найти первый элемент, больший для каждого элемента во входном массиве, вы можете использовать алгоритм upper_bound (пример в C++ http://www.cplusplus.com/reference/algorithm/upper_bound/), чтобы найти первый элемент, который больше

Upper_bound занимает время журнала (N), поэтому общее время для обработки каждого элемента во входном массиве составляет O (NlogN)

Сложность памяти линейна для массива min

Удивительное объяснение!

Watson 10.08.2018 12:05

@MBo не уверен, что я следую за вами ... с приведенной выше идеей я не вычисляю все результаты за один проход, может быть, вы нашли что-то умнее?

arenard 10.08.2018 12:15

@arenard О, да, моя вина. Бинарный поиск или upper_bound в правой части массива min - хорошее решение. Итак, общее время - O(NlogN).

MBo 10.08.2018 12:22

Другие вопросы по теме