Подсчитать количество общих элементов между отсортированным массивом и массивом, отсортированным в обратном порядке

Даны два массива, состоящие из N различных целых чисел, такие, что массивы A[] и B[] отсортированы в порядке возрастания и убывания соответственно, задача состоит в том, чтобы найти количество значений, общих в обоих массивах.

Примеры:

Input: A[] = {1, 10, 100}, B[] = {200, 20, 2}
Output: 0

Input: A[] = {2, 4, 5, 8, 12, 13, 17, 18, 20, 22, 309, 999}, B[] = {109, 99, 68, 54, 22, 19, 17, 13, 11, 5, 3, 1}
Output: 4

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

• Инициализируйте две переменные, скажем, первую как 0 , а вторую как (N – 1) , которые используются для обхода массива A[] и B[] спереди и сзади соответственно.
• Инициализируйте переменную, скажем, count как 0 , которая хранит количество чисел, общих в массиве A[] и B[] .
• Повторяйте цикл до тех пор, пока первое < N и второе > = 0 , и выполните следующие шаги:
  • Если значение A[first] равно B[second] , тогда увеличьте значения count и first и уменьшите значение second .
  • Если значение A[first] меньше, чем B[second] , увеличьте значение first .
  • Если значение A[first] больше, чем B[second] , уменьшите значение second .
• После выполнения вышеуказанных шагов выведите в качестве результата значение count .

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

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