Порядок удаления в задаче Иосифа Флавия за O(N logN)

Даны N детей, стоящих в кругу, ожидающих казни, и число K , означающее, что K-1 детей пропускаются по часовой стрелке, а K ^-й ребенок в круге убивается, а затем выполняется (K+1 ) ^й начинается ребенок, задача состоит в том, чтобы напечатать ребенка, который будет убит на i ^-м ходу, если выполнение начнется с первого ребенка.

Примечание. По умолчанию последний дочерний элемент считается мертвым в конце.

Примеры:

Input: N = 5, K = 2
Output: 3 1 5 2 4
Explanation: 
Initially, the arrangement is {1, 2, 3, 4, 5} and the operations performed are:

1. Counting from 1, the K^th child is 3.  So the 3rd child gets killed. After that, the children left to be executed are {1, 2, 4, 5}, and then execution of child 4 begins.
2. Counting from 4, the K^th child is 1.  So the first child gets killed. After that, the children left to be executed are {2, 4, 5}, and then execution of child 2 begins.
3. Counting from 2, the K^th child is 5. So the fifth child gets killed. After that, the children left to be executed are {2, 4}, and then execution of child 2 begins.
4. Counting from 2, the K^th child is 2.  So the second child gets killed. After that, the child left to be executed is 2, and then execution of child 4 begins.
5. Finally, child 4 is the only remaining child. So the child will be killed.

Input: N = 7, K = 2
Output: 3 6 2 7 5 1 4

Наивный подход: самая простая идея — использовать вектор для хранения положения оставшихся дочерних элементов. Затем выполните итерацию, пока размер вектора больше 1 , и на каждой итерации стирайте нужную позицию из вектора.

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

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

• Инициализируйте упорядоченный набор, скажем, V , и вставьте элементы в диапазоне [1, N] в V .
• Инициализируйте переменную, скажем, pos как 0 , чтобы сохранить индекс удаленного элемента.
• Повторяйте до тех пор, пока размер набора V не станет больше 1 , и выполните следующие шаги:
  • Сохраните размер набора в переменной, скажем, X .
  • Обновите значение pos до (pos + K) % X .
  • Напечатайте элемент, на который указывает pos , в V , а затем сотрите его.
  • Обновите pos до pos%V.size().
• Наконец, после выполнения вышеуказанных шагов выведите последний элемент, хранящийся в начале множества V.

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

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