1

Необходимо разделить список из произвольного количества чисел таким образом, чтобы слева все числа были меньше, чем справа. И посчитать количество таких способов.

То есть, например, [3,2,3,5,8,7,9] можно разделить тремя способами:

[3,2,3]  и [5,7,6,9]
[3,2,3,5] и [8,7,9]
[3,2,3,5,8,7] и [9]

Понимаю, как это сделать с помощью вложенного цикла, но нужно, чтоб было именно O(n).

0

2 ответа 2

4

Tо есть для каждого элемента i вам надо найти максимальный элемент среди [0, i] и минимальный элемент среди [i+1, N] и проверить, что максимальный слева меньше, чем минимальный справа. Это делается за линейное время без проблем, надо только иметь 2 доп массива для максимальных и минимальных элементов.

Код на C#

var input = new[] { 3, 2, 3, 5, 8, 7, 9 };
var maxes = new int[input.Length];
var mins = new int[input.Length];

maxes[0] = input[0];
for (int i = 1; i < input.Length; i++)
    maxes[i] = Math.Max(maxes[i - 1], input[i]);

mins[mins.Length - 1] = input[input.Length - 1];
for (int i = input.Length - 2; i >= 0; i--)
    mins[i] = Math.Min(mins[i + 1], input[i]);

int count = 0;
for (int i = 0; i < input.Length - 1; i++)
    if (maxes[i] < mins[i + 1]) count++;

Console.WriteLine(count);
2
  • 1
    Плюс. Достаточно даже одного массива, например, правых минимумов, а левый максимум считать на втором проходе.
    – MBo
    17 сен 2020 в 2:50
  • @MBo согласен :)
    – tym32167
    17 сен 2020 в 12:09
1

Не представляю как это за O(n) сделать.

n = [3, 2, 3, 5, 8, 7, 9]

for i in range(1, len(n)):
    if max(n[:i]) < min(n[i:]):
        print(n[:i], n[i:])

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.