Нахождение трех элементов в массиве, сумма которого является самой близкой к данному числу
Учитывая массив целых чисел, A1, A2..., включая отрицательные стороны и положительные стороны и другое целое число S. Теперь мы должны найти три различных целых числа в массиве, сумма которого является самой близкой к данному целому числу S. Если там существует больше чем одно решение, любой из них в порядке.
Можно предположить, что все целые числа в диапазоне int32_t, и никакое арифметическое переполнение не произойдет при вычислении суммы. S является ничем специальным, но случайным образом выбранным числом.
Есть ли какой-либо эффективный алгоритм кроме поиска грубой силы для нахождения этих трех целых чисел?
3 ответа
Существует ли какой-либо другой эффективный алгоритм, кроме поиска методом грубой силы, чтобы найти три целых числа?
Да; мы можем решить это за O(n2) время! Во-первых, учтите, что Ваша задача P может быть сформулирована эквивалентно несколько иначе, что устраняет необходимость в "целевом значении":
оригинальной задаче
P: Учитывая массивAизnцелых чисел и целевое значениеS, существует ли тройка изA, которая складывается изS?измененная задача
P': Учитывая массивAизnцелых чисел, существует ли тройка изA, которая складывается в ноль?
Заметьте, что вы можете перейти от этой версии задачи P' из P, вычитая вашу S/3 из каждого элемента в A, но теперь вам больше не нужно целевое значение.
Очевидно, что если мы просто протестируем все возможные 3-ступени, мы решим проблему в O(n3) - это и есть базовый уровень грубой силы. Можно ли сделать лучше? Что, если мы подберем кортежи несколько умнее?
Во-первых, мы потратим некоторое время на сортировку массива, что стоит нам начального штрафа в O(n log n). Теперь мы выполняем этот алгоритм:
for (i in 1..n-2) {
j = i+1 // Start right after i.
k = n // Start at the end of the array.
while (k >= j) {
// We got a match! All done.
if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])
// We didn't match. Let's try to get a little closer:
// If the sum was too big, decrement k.
// If the sum was too small, increment j.
(A[i] + A[j] + A[k] > 0) ? k-- : j++
}
// When the while-loop finishes, j and k have passed each other and there's
// no more useful combinations that we can try with this i.
}
Этот алгоритм работает, размещая три указателя, i, j, и k в различных точках массива. i начинается в начале и медленно продвигается к концу. k указывает на самый последний элемент. j указывает на то, где i начало. Мы итеративно пытаемся просуммировать элементы по их соответствующим индексам, и каждый раз происходит одно из следующего:
- Сумма в точности правильная! Мы нашли ответ.
- Сумма была слишком мала. Переместите
jближе к концу, чтобы выбрать следующее наибольшее число. - Сумма была слишком велика. Переместите
kближе к началу, чтобы выбрать следующее наименьшее число.
Для каждого i указатели j и k будут постепенно приближаться друг к другу. В конце концов, они пройдут мимо друг друга, и в этот момент нам больше не нужно будет ничего пробовать для этого i, так как мы будем суммировать одни и те же элементы, просто в другом порядке. После этого момента мы попробуем следующий i и повторим.
В конце концов, мы либо исчерпаем полезные возможности, либо найдем решение. Видно, что это O(n2), так как мы выполняем внешнее время цикла O(n) и внутреннее время цикла O(n). Это можно сделать субквадратично, если Вы получите действительно фантастический ответ, представляя каждое целое число в виде битового вектора и выполняя быстрое преобразование Фурье, но это выходит за рамки данного ответа.
Примечание: Поскольку это вопрос для интервью, я немного сжульничал здесь: этот алгоритм позволяет выбирать один и тот же элемент несколько раз. То есть (-1, -1, 2) было бы правильным решением, как и (0, 0, 0). Также он находит только ответы exact, а не самый близкий ответ, как указано в заголовке. В качестве упражнения для читателя, я дам вам понять, как заставить его работать только с отдельными элементами (но это очень простое изменение) и точными ответами (что также является простым изменением).
Вероятно, вам придется заменить # на # #, чтобы избежать этого, я думаю, это вызвано тем, что # определяется как ключевое слово Coldfusion.
-121--5044800-Для коллекций примитивов следует использовать запрос HQL следующим образом:
from Item item join item.labels lbls where 'hello' in (lbls)
PS: «» join «» требуется, поскольку «» labels «» является вариантом OneToMany или ManyToMany, скобки требуются, поскольку «» lbls «» является коллекцией
-121--1599530-Как насчет чего-то подобного, что является O (n ^ 2)
for(each ele in the sorted array)
{
ele = arr[i] - YOUR_NUMBER;
let front be the pointer to the front of the array;
let rear be the pointer to the rear element of the array.;
// till front is not greater than rear.
while(front <= rear)
{
if(*front + *rear == ele)
{
print "Found triplet "<<*front<<","<<*rear<<","<<ele<<endl;
break;
}
else
{
// sum is > ele, so we need to decrease the sum by decrementing rear pointer.
if((*front + *rear) > ele)
decrement rear pointer.
// sum is < ele, so we need to increase the sum by incrementing the front pointer.
else
increment front pointer.
}
}
Это находит, если сумма 3 элементов точно равна вашему числу. Если вы хотите быть ближе всего, вы можете изменить его, чтобы запомнить наименьшую дельту (разница между вашим количеством текущего триплета) и в конце напечатать триплет, соответствующий наименьшей дельте.
Очень простые n ^ 2 * Решение logn: сортировать входной массив, затем пройти через все пары A I , A j (N ^ 2 Время), а для каждой пары проверьте ли (S - A I - A j ) в массиве (входное время).
Другое решение O (S * N) использует классическое динамическое программирование .
Короче говоря:
создать 2-D массив V [4] [S + 1]. Заполните его таким образом, что:
v [0] [0] = 1, v [0] [x] = 0;
v 1 [A I ] = 1 для любого i, v [x] = 0 для всех остальных x
v [2] [A I + A J ] = 1, для любого i, j. V [2] [x] = 0 для всех других x
v [3] [сумма любых 3 элементов] = 1.
, чтобы заполнить его, итерации через I , для каждого A I Имеет итерацию через массив справа налево.