#arrays #performance #big-o
Вопрос:
Подводя итог: мне нужна помощь в поиске эффективного способа нахождения кратчайшего или наиболее краткого подмассива с наибольшим числом возрастающих чисел (например, 1, 2, 3…), допускающего случайные числа между ними.
Длинная форма: Я получаю «числа» в несколько случайном порядке, но мне нужно найти самый длинный отрезок возрастающих чисел, но также важно, чтобы они занимали как можно меньше места. Поэтому мне нужен самый краткий подмассив из самого длинного ряда возрастающих чисел. Между ними могут быть и другие ложные числа, которые игнорируются. Например, [1, 2, 1, 3] является допустимым запуском 1-3 и является более кратким, чем также допустимый [1, 2, 1, 1, 3]. И более длительный пробег должен быть более важным, если это возможно (например, 1-4 победы над 1-3), даже если подмножество значительно длиннее.
Результатом будут индексы подмассива. 1 Для наших целей запуск всегда будет начинаться с, и результатом может быть пустой массив, если 1 его нет. Я всегда буду заранее знать, какими могут быть минимальные (1) и максимальные значения, но не буду знать, будут ли все эти числа присутствовать во входном массиве.
Примеры
Входной Массив: [4, 3, 2, 1, 1]
Ожидаемый результат: [3:4] (нулевая база)
Примечания: Числа должны быть в порядке возрастания, и запуск должен начинаться с 1, поэтому первый экземпляр
1-это единственное, что находится в возвращаемом поддиапазоне.
Входной Массив: [4, 1, 2, 3, 1, 1, 3, 2, 3, 1, 4, 1, 2]
Ожидаемый результат: [5:10]
Примечания: Существует несколько 1-4 запусков (т. е. [1:10], [4:10], [5:10]), но побеждает тот, кто короче.
Входной Массив: [1, 2, 2, 3, 3, 4, 1, 2, 3]
Ожидаемый результат: [0:5]
Примечания: Несмотря на то, что последние 3 числа являются более кратким подмассивом, преобладает более длительный период. Кроме того, последние 4 не являются порядком возрастания.
Я пробовал думать о раздвижных окнах, но они, кажется, работают лучше, когда порядок не важен, но в моем случае мне нужно знать, что у меня самая короткая восходящая группа из самых длинных. Таким образом, это означает, что мне нужно сначала знать, какой самый длинный восходящий пробег (вероятно?), а затем какой самый короткий вариант этого.
Я немного растерялся в том, как справиться с этим просто и эффективно. Есть ли эффективный способ сделать это, или это просто будет O(n^2) на всем пути?
Также, если есть лучший обмен стеками для этого вопроса, пожалуйста, дайте мне знать.
Спасибо!
Комментарии:
1. «с учетом случайных чисел между ними». < — это означает, что числа не обязательно являются последовательными . Пожалуйста, уточните.
2. «самый краткий подмножество» — пожалуйста, определите «краткий». Насколько мне известно, «краткий»-это не строго определенный термин, используемый в информатике.
3. @Dai, подумайте «экономный» как синоним «лаконичный». Я имею в виду последовательность в числовой строке, но не обязательно последовательность внутри массива.
4. Я бы выбрал вариант проблемы с наибольшей возрастающей подпоследовательностью. Для этого существует хорошо известный
O(nlogn)алгоритм (см., например, здесь: geeksforgeeks.org/… ), надеюсь, его можно немного исказить, чтобы определить самую короткую восходящую группу самого длинного пробега.