Задача ШАДа.

Эта задача была на собеседовании в ШАД в 2023 году. Я считаю задача одна из коварных по сравнению с остальными, подумайте над этой задачей и думаю вы поймете о чем я.

Задача:
Дается массив из целых чисел, вернуть True, если можно за один swap двух чисел сделать массив отсортированным (по возрастанию или по убыванию). В массиве могут быть повторы.

Решение: (Настоятельно рекомендую перед этим подумать)

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


Пойдем с конца, возьмем отсортированный массив по возрастанию и сделаем swap двух чисел, как будет выглядит массив (например если рисовать график) ?

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

Назовем позиции i особенными если, a[i - 1] > a[i].

-Если особенных позиций больше 2 ответ False.

-Если такой позиции ровно 1, то вы должны сделать swap чисел a[i] и a[i - 1] и проверяете что массив отсортирован по возрастнанию.

-Если таких позицй ровно 2 (пусть это i1 и i2) то вы должны сделать swap чисел a[i1 - 1], a[i2] после проверить, что массив стал отсортированный.


Мы упустили случай, когда массив изначально был отсортирован по убыванию. Но у нас есть решение (функция) выше, нам надо вызывать ровно это же решение, умножив все элементы массива на -1.

Время работы алгоритма O(n).

Для тех кто готовится к собесу в ШАД оставлю полезные задачи, которые встречались в прошлом году.

https://t.me/algoses/6
https://t.me/algoses/12
https://t.me/algoses/29
https://t.me/algoses/33
https://t.me/algoses/37
https://t.me/algoses/90
https://t.me/algoses/95