Лучший алгоритм для группировки и добавления в список следующего шаблона

Question

Давайте рассмотрим, что у нас есть объекты в списке как

listOfObjects = [a,b,ob,ob,c,ob,c,ob,c,ob,ob,c,ob]

, мы должны сгруппировать их как

[ob,ob,c,ob,c,ob] from index 2 to 7
[ob,ob,c,ob] from index 9 to 12

, то есть группа начинается , если мы имеем два ob'а вместе , как в индексах 2 и 7, и заканчивается перед 'c', имеющим два ob, следующих за , как в индексе 8 , имеющем 'c ', за которым следуют два' ob's или , если список заканчивается .

Так что будет лучшим алгоритмом для получения вышеуказанного (в Java)?

Answer 1

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

Вы можете выполнить эту задачу простым обходом, отслеживая следующие 3 элемента (конечно, заботясь о том, чтобы вы не выходили за рамки списка) и заканчивая группу, проверяя указанную вами стратегию.Если рядом с текущим элементом нет 3 элементов, вы просто заканчиваете свою группу (как вы указали в своей стратегии) ​​

Таким образом, временная сложность этого алгоритма будет O(n).Не будет лучше, чем это.

Answer 2

Я думаю, что стек - подходящая структура данных.

все будет хорошо, когда вы положите 'ob' в стек.

вам также понадобится переменная 'count'.