Проверьте, можно ли отсортировать массив, поменяв местами соседние элементы так, чтобы каждый элемент менялся местами четное количество раз.

Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы проверить, можно ли отсортировать массив, переставляя соседние элементы местами любое количество раз так, чтобы каждый элемент массива менялся местами четное число раз.

Примеры:

Input: arr[] = {4, 3, 2, 5}
Output: Yes
Explanation:
Below are the possible order of swapping to make the array sorted:

1. Choose the indices 0 and 1 modifies the array to [3, 4, 2, 5]. Now, the frequency of swapping of {2, 3, 4, 5} is {0, 1, 1, 0} respectively.
2. Choose the indices 1 and 2 modifies the array to [3, 2, 4, 5]. Now, the frequency of swapping of {2, 3, 4, 5} is {1, 1, 2, 0} respectively.
3. Choose the indices 0 and 1 modifies the array to [2, 3, 4, 5]. Now, the frequency of swapping of {2, 3, 4, 5} is {2, 2, 2, 0} respectively.

Therefore, every array element is swapped even number of times and the given array is sorted. Hence, print Yes.

Input: arr[] = {1, 2, 3, 5, 4}
Output: No

Подход: Данную задачу можно решить, заметив, что два соседних четных или нечетных элемента индекса можно поменять местами, так как нет ограничений на количество перестановок без изменения среднего элемента. Поэтому идея состоит в том, чтобы переставить элемент массива по соответствующим четным и нечетным индексам и проверить, отсортирован ли сформированный массив или нет. Выполните следующие шаги, чтобы решить данную проблему:

• Сохраните все элементы массива arr[i] с нечетными индексами в другом массиве, например, odod[] .
• Сохраните все элементы массива arr[i] с четными индексами в другом массиве, скажем, даже[] .
• Отсортируйте массивы нечетные[] и четные[] в порядке возрастания.
• инициализируйте две переменные, скажем, j и k как 0 , которые используются для обхода массивовod [] и even[] .
• Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
  • Если значение i нечетное, то поместите элементodod[j] в массив res[] и увеличьте значение j на 1 .
  • Если значение i четное, то поместите элемент even[k] в массив res[] и увеличьте значение j на 1 .
• После выполнения вышеуказанных шагов, если массив res[] отсортирован, то выведите Yes . В противном случае выведите Нет .

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

Сложность времени : O(N*log N)
Вспомогательное пространство: O(N)