Циклически отсортированный массив (отсортированный и повернутый массив)

Массивы с циклической сортировкой — это массивы, отсортированные по возрастанию или убыванию, а затем повернутые на определенное количество шагов.

Давайте рассмотрим пример, чтобы узнать больше о циклически отсортированных массивах:

Consider an array: arr[] = {23, 34, 45, 12, 17, 19}
The elements here, {12, 17, 19, 23, 34, 45} are sorted ‘In-order’ but they are rotated to the left by 3 times.

Восходящий циклически отсортированный массив :

• Рассмотрим массив, отсортированный в порядке возрастания: arr[] = {12, 17, 19, 23, 34, 45}
• Если приведенный выше массив повернуть на 3 шага влево, то результирующий массив будет циклически отсортированным по возрастанию: {23, 34, 45, 12, 17, 19}

Убывающий циклически отсортированный массив:

• Рассмотрим массив, отсортированный в порядке убывания: arr[] = {35, 26, 11, 9, 5, 3}
• Если приведенный выше массив повернуть на 3 шага влево, то результирующий массив будет циклически отсортированным по убыванию: {9, 5, 3, 35, 26, 11}

Давайте проверим с помощью приведенной ниже задачи, отсортирован ли данный массив по кругу или нет:

Постановка задачи:

Учитывая массив arr[] длины N , задача состоит в том, чтобы проверить, является ли данный массив циклически отсортированным или нет, нам нужно проверить, является ли данный массив повернутой формой отсортированного массива.

• В массиве с круговой сортировкой по возрастанию будет не более одного случая, когда элемент непосредственно перед текущим элементом будет больше, чем текущий элемент, т. е. arr[ i – 1 ] > arr[ i ] . Поэтому нам нужно подсчитать общее количество таких случаев, и если количество больше 1, то результат будет ложным, иначе результат будет истинным, что означает, что массив отсортирован по кругу .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(n)

Вспомогательное пространство: O(1)

Similarly, we can do the above operation for descending circularly sorted array. In this case we need to consider the count of the case where, arr [i-1] < arr[i]. 

Статьи по Теме:

• Проверить, отсортирован ли массив и повернут ли он
• Найдите счетчик вращения в массиве с сортировкой по вращению
• Поиск элемента в отсортированном и повернутом массиве
• Найдите минимальный элемент в отсортированном и повернутом массиве
• Максимальный элемент в отсортированном и повернутом массиве