Учитывая следующую проблему, я был бы признателен за любые исправления, так как у меня нет решения на текущий вопрос (взято из одного из моих профессорских экзаменов !!!) :
Примечание: это не домашнее задание !
Задача:
Даны два отсортированных массива A
(длиной n
) и B
(длиной m
), где каждый
элемент (в обоих массивах) является действительным числом и числом X
(также действительным числом),
мы хотели бы знать, существует ли или нет ∈ A
и b ∈ B
, например:
a + b = X
, в O(n+m)
время работы .
Решение:
Во-первых, мы начинаем проверку с конца обоих массивов, так как нам не нужны числа больше, чем X
:
k = m
в то время как A[i] > X , i = i-1
Определить j = 0 .
Теперь начните работать с текущего i
в A
и из j
в B
:
, пока i > 0, j < k
:если A[i]+B[j] == X
, то вернуть обе ячейкиj = j+1 , i = i -1
В итоге у нас будет либо два элемента, либо мы выйдем за пределы одного
или оба массива, что означает, что не существует двух элементов, таких a + b = X
.
Будем признательны за любые замечания.
Спасибо