Проверьте, одинакова ли последовательность элементов в данных двух массивах или нет.

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

Учитывая два массива A и B каждый размером N , задача состоит в том, чтобы проверить, является ли последовательность обоих массивов одинаковой или нет. Если последовательность обоих массивов одинакова, печатается Да , в противном случае печатается Нет .

Примеры:

Input: A[] = { 10, 12, 9, 11 }, B[] = { 2, 7, -3, 5 };
Output: Yes
Explanation: In both the arrays 2nd element is greater than the first one.
The 3rd element is smaller than the 2nd and the last element is greater than the 3rd one.

Input: A[] = { 1, 2, 3, 4 }, B[] = { 1, 3, 2, 4 };
Output: No

Подход: выполните следующие шаги, чтобы решить эту проблему:

  • Создайте вектор пар, скажем, arr[] и вставьте в него элементы A и B.
  • Каждый элемент вектора arr, т.е. arr[i], имеет тип {A[i], B[i]}.
  • Теперь отсортируйте этот вектор arr по первому элементу.
  • После сортировки проверьте, должен ли второй элемент каждой пары в arr быть частью отсортированной последовательности.

 arr[i-1].second < arr[i].second, for each i.

  • Если да, то выведите Yes , иначе выведите No.

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


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

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