Найти сумму x из элементов из 4 последовательностей
Это моя проблема:
Учитывая число x и 4 последовательности A, B, C и D, каждое из n чисел, решают, существуют ли некоторые числа a из A, b из B, c из C и d из D, такие что x = a+b+c+ д. Разрешены операции сравнения, добавления и замены. Разработайте эффективный алгоритм для решения этой проблемы с наихудшим временем выполнения менее n^4.
Я понятия не имею, с чего начать, и буду признателен за помощь!
1 ответ
Вы можете сделать следующее:
- создать массивы парных сумм AB=A+B, CD=C+D, суммируя каждую пару между A и B и одинаковую для C и D (AB и CD являются массивами из n^2 элементов каждый) - O (n^2)
- Сортировать массивы AB, CD - O(n^2 log(n)) (благодарность user58697 за этот подход. Ранее я предлагал другой подход, который, как мне казалось, будет более сложным, но (с) он указал на мою ошибку.)
- Назначить индексы abi = (n^2-1), cdi = 0
Изучите AB[abi]+CD[cdi], проверьте условия и индексы увеличения / уменьшения
- Вычислить сумму =AB[abi]+CD[cdi]
- Если сумма равна x: такая комбинация существует! (алгоритм остановки)
- Если сумма
- Если сумма> x: уменьшить значение abi (--abi)
- Если (abi < 0) ИЛИ (cdi >= n^2): НЕТ ТАКОЙ КОМБИНАЦИИ! (алгоритм остановки)
- Вернитесь к 4.1.
Каждый раз, когда мы выполняем шаг 4, индекс либо увеличивается, либо уменьшается (или алгоритм останавливается), поэтому мы выполняем шаг 4 максимально 2*n^2 раза (количество элементов в обоих массивах) - O (n^2)
Таким образом, в целом мы имеем O(n^2 log(n))