Мне дали массив. Мне нужно найти последнее (крайнее правое) меньшее или равное число для каждого элемента в массиве.
Например:
2 5 1 6 4 7
2 имеет последний меньший или равный номер 1,
5 имеет последний меньший или равный номер 4, а не 1 и т. д.
Другой пример:
5 100 8 7 6 5 4 3 2 1
Здесь каждый элемент имеет последний меньший или равный номер 1. Я знаю наивный подход, то есть O (n²), но мне нужен лучший подход.
@ LasseVågsætherKarlsen, для элемента мы проверяем все те элементы справа, которые меньше, и выбираем последний меньшего размера.
Я думаю, он имел в виду, что для каждого числа ему нужно найти в оставшемся массиве число, которое меньше текущего, и последнее такое число является последним минимумом.
Я предполагаю, что последний минимум не существует для наименьшего числа, например, для 1
не будет последнего минимума
@Ishpreet, для 1 можно просто 1.
Можете ли вы объяснить, какой будет наименьший минимум в случае неуникального списка, например, для 2 4 2 3 4
, какой будет наименьший минимум для 2?
@Ishpreet, Начиная с последнего, у нас есть последний минимум в индексе 2, если массив имеет 0-индекс.
Какой должен быть ответ? Другой массив?
Вы могли пойти справа налево и построить минимальный массив из минимального числа до сих пор.
Для вашего примера 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
Удивительное объяснение!
@MBo не уверен, что я следую за вами ... с приведенной выше идеей я не вычисляю все результаты за один проход, может быть, вы нашли что-то умнее?
@arenard О, да, моя вина. Бинарный поиск или upper_bound
в правой части массива min - хорошее решение. Итак, общее время - O(NlogN)
.
Пожалуйста, объясните логику «последнего минимума», как вы пришли к 1 как «последнему минимуму» для 2?