Найдите, есть ли элементы (x, y, z) в несортированном массиве так, чтобы x + y = z
Для несортированного массива A [1 ... n]. Напишите алгоритм, который возвращает истину, если в A есть три элемента A [i], A [j], A [k], так что A [i] + A [j ] = A [k], иначе алгоритм должен вернуть false (обратите внимание, что может быть A [i] = A [j] и это допустимо). Необходимое время - O (n ^ 2). Я придумал алгоритм, который работает в O (n ^ 2 * log (n)). Мой алгоритм сортирует массив, а затем для каждой пары из двух элементов x, y использует двоичный поиск, чтобы определить, существует ли элемент x + y. Есть ли более быстрое решение, которое занимает O (n ^ 2)?
знаете ли вы, существует ли такое решение на самом деле или нет? Подходит ли эта задача для средней школы или университета?
Я слышал об этой проблеме в своем университете, и есть более быстрое решение наихудшего случая. Я не могу придумать такой.
Есть ли ограничения на ввод? Например диапазон возможных значений ...
ввод - действительные числа
Ответы 2
Вы можете создать хеш-таблицу элементов A, для которых выполняется поиск O (1), и использовать ее для поиска x + y.
В хеш-таблице на самом деле нет поиска O (1), это называется псевдоконстантой, поскольку такое поведение работает только для ограниченного количества чисел. Если вы продолжите добавлять все больше и больше чисел, оно начнет расти до O (n)
Это также одна из причин, почему большинство баз данных обычно используют сбалансированные деревья с поиском log (n) для индексов, а не хеш-таблиц.
Таким образом я улучшаю среднее время. Возможно ли получить время наихудшего случая O (n ^ 2)?
@Lev - нет, хеш-таблицы имеют реальную сложность O(n) для поиска. (по сложности мы говорим о том, что такое сложность для неограниченного количества номеров)
@libik Да, поэтому хеш-таблицы дают наихудший случай O (n ^ 3). Это медленное решение наихудшего случая
@libik то, что вы говорите, в целом верно для общей хеш-таблицы и неограниченного ввода. Но здесь указан размер ввода, поэтому мы не будем «добавлять все новые и новые числа», у нас их только n. Таким образом, мы выделяем хеш-таблицу только один раз, не нужно переделывать. Поэтому это решение с хеш-таблицей как в среднем, так и в худшем случае будет O(n).
Вы можете сначала отсортировать массив - O(nlogn)
Далее все сводится к нахождению двух сумм для A[k] среди элементов A[0] .. A[k-1] для любого элемента A[k].
Две суммы для отсортированного массива можно найти в O(n) с помощью метода двух указателей, например:
boolean searchSum( int k, int[] A ) {
if ( k > A.length - 1 || k < 2 ) return false;
i = 0, j = k-1
while ( i < j ) {
if (A[i] + A[j] == A[k])
return true;
else if (A[i] + A[j] < A[k])
i++;
else
j--;
}
return false;
}
для каждого k это O(k-1), а общая сложность должна быть O(n^2).
вы могли бы вызвать searchSum как:
boolean myMethod( int[] A ) {
sort(A);
for ( int i = A.length - 1; i >= 2; i-- ) {
if ( searchSum( i, A ) ) {
return true;
}
}
return false;
}
@libik серьезно? значение k должно быть индексом в массиве. Этот метод на самом деле является своего рода прототипом того, как проблема может быть решена, конечно, я могу сломать любой метод бессмысленным вводом.
Я хочу достичь наихудшего случая O (n ^ 2). Поэтому решения с хеш-таблицами или другими вероятностными структурами данных не помогают.