Количество ходов, необходимых между массивами для завершения обхода в отсортированном порядке

Даны два отсортированных массива, X[] размера N и Y[] размера M , имеющие уникальные значения. Задача состоит в том, чтобы подсчитать общее количество ходов, необходимых между массивами для обхода всех элементов обоих массивов в порядке возрастания, если изначально обход начинается с массива X[] .

Примеры:

Input: X[] = {1}, Y[] = {2, 3, 4}
Output: 1 
Explanation: Only 1 move is required after traversing the X array and then move to the 0 index of the Y array and traverse its rest of the values.

Input: X[] = {1, 3, 4}, Y[] = {2, 5, 6}
Output: 3

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

• Инициализируйте два указателя, скажем, i как 0 и j как 0 , указывающих на массивы X[] и Y[] соответственно.
• Инициализируйте другую переменную total_moves как 0 , чтобы сохранить необходимое количество ходов.
• Поскольку обход всегда начинается с массива X[] , поэтому сначала сравните значения по текущему индексу. Возникают два случая:
• Если в настоящее время присутствует в массиве X[] :
  • Если X[i] < Y[j] , просто увеличьте индекс i .
  • Если X[i] > Y[j] , увеличьте total_moves и индекс j .
• Если в настоящее время присутствует в массиве Y[] :
  • Если Y[j] < X[i] , увеличить индекс j .
  • Если Y[j] > X[i] , увеличьте total_moves и индекс i .
• Повторяйте вышеуказанные шаги, пока не будет завершен любой из обходов массива.
• После завершения вышеуказанного цикла значение total_moves будет увеличиваться при следующих двух условиях:
  • Если обход заканчивается в массиве X и j < M , тогда увеличьте total_moves на 1 .
  • Если обход заканчивается в массиве Y и i < N , тогда увеличьте total_moves на 1 .
• В качестве результата выведите значение total_moves .

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

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