Вставить элемент в отсортированный и повернутый список

Question

Дан список отсортированных и повернутых элементов. Элементы сортируются в порядке по возрастанию или по убыванию . Например - у меня есть список отсортированных элементов следующим образом

10,12,14,16,18,20,51,53,54,59

Теперь этот список поворачивается на X раз, а затем выглядит следующим образом.

51,53,54,59,10,12,14,16,18,20

Если вы хотите вставить элемент в этот список, какой способ будет наиболее эффективным?

Если элемент для вставки равен 13, если список перемещается линейным образом, ложная вставка может произойти в диапазоне от 59 до 10.

Я не ожидаю никакого кода, скорее я жду обсуждения алгоритма. Значение 21 может быть вставлено как первый / последний элемент. Учет граничных условий, таких как - вставляемый элемент, первый и последний элемент имеют одинаковое значение.

Answer 1

Это может быть решено в журнале (N) времени.Вкратце:

1. Используйте бинарный поиск, чтобы найти самый большой / самый маленький элемент списка.Это занимает O (logN).Реализация проста, просто сравните элемент, который вы просматриваете, с первым элементом списка.
2. Используйте бинарный поиск для вставки нового элемента, используя только необходимую часть списка.Это также занимает O (logN).

Подробнее о пункте 1: Скажем, вам нужно найти самый большой элемент в 51,53,54,59,10,12,14,16,1820.

Сначала вы выбираете средний элемент (скажем, будет 12).12 меньше 51, поэтому самый большой элемент находится слева от 12. Вы делите интервал пополам и получаете 54. 54 больше 51, поэтому самый большой элемент находится между 54 и 12. И так далее

Answer 2

Реальный вопрос, конечно, касается структуры данных и требуемой эффективности.

• Что такое порядок (возрастание / убывание)
• Где это "минимум"

Обратите внимание, что вам нужно знать о порядке, иначе 4,2 можно интерпретировать как:

• 2,4 поднимается и поворачивается один раз
• 4,2 по убыванию

Из 3 элементов можно догадаться, что 4,2,3 поднимается и поворачивается один раз из-за способа, которым максимальные и минимальные значения установлены вместе.

Действительно, вам, вероятно, следует использовать Круговую структуру, которая облегчит вращение. Тогда вы можете поддерживать Accessor для этой структуры:

• Что указывает на минимум
• Который указывает на текущее начало

Учитывая минимум, легко (одно сравнение с его правым соседом) узнать, каков порядок. И с этого момента вставка в круговую структуру также проста.

Answer 3

Предполагая, что ваш список обеспечивает эффективный произвольный доступ, это двоичный поиск со смещением.Если вы нашли правильный индекс, вы перемещаете позицию индекса элемента 1 влево.Это имеет сложность O (log n) для поиска и O (n) для операции копирования списка.

Answer 4

Следите за минимальным элементом во время X «поворотов». Затем используйте бинарный поиск в соответствующей половине.

Answer 5

Одно решение, которое я придумал,

1. Проверьте граничные условия, такие как

• Если новый элемент является ч / б первым и последним элементом ИЛИ наоборот
• Если новый элемент равен либо первому ИЛИ последнему элементу

Если любое из вышеперечисленных условий выполнено, вставьте элемент на первое место.

2. Возьмите средний элемент

• проверить, если новый элемент == Средний элемент - вставить новый элемент в эту позицию
• Проверьте, является ли новый элемент ч / б Средний элемент и самый правый ИЛИ это ч / б самый левый и самый правый элемент.

3.Compute номер элемента ч / б левый-средний ИЛИ средний-правый на основе вышеуказанных условий.

• Если число элементов <= 2, вставить новый элемент ч / б Левый-Средний <em>ИЛИ Правый-Средний
• В противном случае вычислите новый левый, средний и правый элемент и выполните шаг 2.