Для заданного числа X найти два элемента в двух отсортированных массивах таких A[i]+B[j] = X в O(n+m)

Учитывая следующую проблему, я был бы признателен за любые исправления, так как у меня нет решения на текущий вопрос (взято из одного из моих профессорских экзаменов !!!) :

Примечание: это не домашнее задание !

Задача:

Даны два отсортированных массива A(длиной n) и B(длиной m), где каждый

элемент (в обоих массивах) является действительным числом и числом X(также действительным числом),

мы хотели бы знать, существует ли или нет ∈ Aи b ∈ B, например:

a + b = X, в O(n+m)время работы .

Решение:

Во-первых, мы начинаем проверку с конца обоих массивов, так как нам не нужны числа больше, чем X:

  • i = n
  • k = m

  • в то время как A[i] > X , i = i-1

  • в то время как B[k] > X , k = k-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.

Будем признательны за любые замечания.

Спасибо

6
задан JAN 27 June 2012 в 14:38
поделиться