Блог

Главная - Вопросы по программированию - Алгоритм поиска трех элементов, сумма которых равна нулю в O(n логарифмической n) сложности по времени

Алгоритм поиска трех элементов, сумма которых равна нулю в O(n логарифмической n) сложности по времени

#arrays #algorithm #time-complexity

Вопрос:

Предположим, что входной массив из n целых чисел содержит только целые числа в диапазоне от-5000n до 6000n. Нам нужно найти алгоритм, который определит, содержит ли массив три элемента, сумма которых равна нулю, за O(n log n) времени.

Мой Подход:

 1. Sort in O(n log n) time.
2. Run a loop in O(n) time
3.     Fix two left and right pointers in the sorted array as the two endpoints
4.     find = SUM - (A[left]   A[right])
5.     Search for the third element (find) using binary search in O(log n)
6.     if found then return TRUE
7.     else 
8.

Я застрял на шаге 8, что если алгоритм двоичного поиска возвращает значение false, то как следует настраивать левый и правый указатели?

Кроме того, будет ли работать весь алгоритм, чтобы найти три элемента, сумма которых равна нулю, в каждом случае, поскольку я не оцениваю все возможные комбинации?

Подсказка — была дана как использование полиномиального алгоритма FFT Ref1 FFT, Ref2 FFT

Комментарии:

1. что вы подразумеваете под n в этих числах-5000n и 6000n?

2. не могли бы вы, пожалуйста, поделиться ограничениями этой проблемы?

3. [-5000n, 6000n] — это диапазон целых чисел, которые может содержать массив.

4. если вы хотите O(n^2) soln, я поделюсь им с вами

5. Если возможно, если поднимите вопрос, иначе в следующий раз я не смогу опубликовать сообщение.

Ответ №1:

Вы не на пути к алгоритму O(N log N). Ваш алгоритм будет либо O(N 2), либо нарушен, в зависимости от того, как вы его закончите.

Этот вопрос должен быть решен с помощью свертки БПФ, как это:

  1. Выделите массив размером W, где W-степень 2 и больше 22001N.
  2. Заполните массив нулями, а затем установите array[v 5000N]=1 для каждого значения v во входном массиве.
  3. Сверните массив с самим собой: вычислите БПФ, возведите в квадрат каждое полученное значение, а затем вычислите IFFT.
  4. Для каждого значения v во входных данных проверьте, не превышает ли ifft[10000N-v] > 0. Если это так, то во входных данных есть два числа, которые складываются в-v. Отсортируйте входной массив и используйте обычный поиск с двумя указателями, чтобы найти эти два других числа.
Метки: ,