Сортировка массива путем разделения на подмассивы, где каждый элемент принадлежит только подмассиву

Опубликовано: 21 Сентября, 2022

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

  • Разбить массив arr[] ровно на Y(1 <= Y <= N) непустых подмассивов так, чтобы каждый элемент принадлежал ровно одному подмассиву.
  • Переупорядочивайте подмассивы в любом произвольном порядке.
  • Объедините переупорядоченные подмассивы.

Примеры:

Input: arr[ ] = {6, 3, 4, 2, 1}, Y = 4
Output: Yes
Explanation:
The operations can be performed as:

  • Split the array into exactly 4 non-empty subarrays: {6, 3, 4, 2, 1} -> {6}, {3, 4}, {2}, {1}
  • Reorder the subarrays: {6}, {3, 4}, {2}, {1} -> {1}, {2}, {3, 4}, {6}
  • Merging the subarrays: {1}, {2}, {3, 4}, {6} -> {1, 2, 3, 4, 6} (sorted)

Input: arr[ ] = {1, -4, 0, -2}, Y = 2
Output: No

Подход: основная идея заключается в том, что если минимальное количество разбиений, необходимых для сортировки данного массива arr[] , меньше или равно Y, то всегда можно отсортировать массив. Кроме того, необходимое количество разбиений должно быть равно количеству минимального количества разбиений, необходимых для разделения массива на минимальное количество неубывающих подмассивов.

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

Временная сложность: O (N Log N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ