Найдите массив B, по крайней мере, с элементами arr[i] в B, не равными B[i]

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

Учитывая массив arr[] размера N , задача состоит в том, чтобы найти массив размера N , такой, что для каждого i -го элемента массива arr[] выходной массив должен содержать по крайней мере элементы arr[i] , которые не являются равно i -му элементу выходного массива. Если такого массива не существует, то выведите « Impossible ».

Примеры:

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

Input: N = 10, arr[] = {7, 7, 7, 7, 7, 9, 8, 8, 7, 9}
Output: 4 4 4 5 5 1 3 3 5 2

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

  • Инициализируйте массив, скажем, res[] размера N+5, для хранения выходного массива.
  • Кроме того, инициализируйте массив пар, скажем, V размером N+5, где V[i] хранит пару количества элементов, равное res[i] , и индекс i.
  • Выполните итерацию в диапазоне [1, N], используя переменную i, и на каждой итерации присвойте значение пары {N-arr[i], i} переменной V[i].
  • Отсортируйте массив пар в порядке возрастания.
  • Инициализируйте две переменные, скажем, l и r равными 0 для обхода массива.
  • Переберите диапазон [0, N-1], используя переменную l , и выполните следующие шаги:
    • Переберите диапазон [l, N-1], используя переменную r , и выполните следующие действия:
      • Если V[r + 1].first не равно V[r]. сначала , а потом разорвать петлю.
    • Если количество одинаковых элементов, то есть (r-l+1) , не делится на V[l].first, тогда выведите « Impossible » и вернитесь.
    • Инициализируйте переменную, скажем, X , как 1 , чтобы присвоить значения массиву res[].
    • Переберите диапазон [l, r], используя переменную i , и выполните следующие шаги:
      • Перебрать диапазон [i, i+V[l].first] , используя переменную j , а затем в каждой итерации присвоить X значению res[V[j].second] .
      • Увеличьте i на V[l].first и X на 1 .
    • Обновите значение l до r+1 .
  • Наконец, после выполнения вышеуказанных шагов, напечатайте массив res[].

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

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

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