Подсчет элементов массива, которые встречаются перед любым значением префикса другого массива

Опубликовано: 25 Февраля, 2023

Учитывая два массива A[] и B[] размером N каждый, задача состоит в том, чтобы найти количество элементов в массиве B[] , которые встречаются перед любым элементом, который присутствовал перед ним в массиве A[] .

Пример:

Input: N = 5, A[] = {3, 5, 1, 2, 4}, B[] = {4, 3, 1, 5, 2}
Output: 2
Explanation: Array A represent that 3 comes first then followed by 5, 1, 2, 4.
In array B, 4 must comes after 1, 2, 3, 5 but 4 comes before them. 
The value 1 is also in invalid order. It comes before 5.

Input: N = 3, A[] = {1, 3, 2}, B[] = {2, 1, 3}
Output: 1

Подход: Задача может быть решена на основе следующей идеи:

Find the number of elements that are present after all the elements that were present in its prefix in array A[]. Then the remaining elements are the ones that do not follow the rule.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Инициализируйте i = 0 и j = 0 для перебора массивов A[] и B[] соответственно.
  • Пока i и j меньше N :
    • Увеличивайте j до тех пор, пока B[j] не станет таким же, как A[i] или j не выйдет за границы размера массива.
    • Если A[i] и B[j] одинаковы, то B[j] удовлетворяет условиям. Поэтому увеличьте счетчик (скажем, C ) для этого элемента.
    • После вышеуказанной итерации увеличьте значение i , чтобы оно указывало на следующие элементы в массиве A[].
  • Когда цикл завершится, верните значение (NC) в качестве требуемого ответа.

Ниже приведена реализация описанного выше подхода.

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

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