Найдите пару элементов массива с данной суммой и продуктом в O (n*log (n))
Позвольте A быть массивом n положительных целых чисел и k данное целое число.
Я ищу алгоритм, чтобы найти, существует ли пара элементов в массиве, таким образом что A[i] * A[j] == k и A[i] == A[j] + k. Если существует такая пара, алгоритм должен возвратить их индекс.
Это - осуществление домашней работы, и нам говорят, что существует O (n*log (n)) решение.
5 ответов
Вот несколько уточненное решение Graphics Noob'а.
Также, это скорее O(N) (предполагая, что хэширование не подведет нас), а не O(N*log(N)).
Result findMultiplicationIndices(int[] A, int[] B, int k)
{
HashMap<Integer,Integer> aDivisors = new HashMap<Integer,Integer>();
for(int i=0;i<A.length;i++)
{
int a = A[i];
if(a!=0)
{
int d = k/a;
if(d*a == k)
aDivisors.put(d, i);
}
}
for(int i=0;i<B.length;i++)
{
Integer ai = aDivisors.get(B[i]);
if(ai != null)
return new Result(ai, i);
}
return null;
}
Первое, что приходит в голову:
Make a Map<Integer, Integer>
for each number a in A:
if (k / a) is a key in the HashMap:
output the index of a, and HashMap.get(k/a)
else
HashMap.add(a, indexof(a))
Итак, это O(n) для обхода массива и O(log n) для поиска ключа в карте (предполагается, что вы использовали TreeMap, HashMap может быть лучше в лучшем случае, но хуже в худшем)
Edit: I guess that only answer a) but you get the idea
Sort the array. Also build a permuted index array by initializing an auxiliary array to 0, 1, 2 ... n and swapping indices every time you swap elements in the array, Time O(nLog(n))
for each element a[i] in array, Time O(n)
Binary Search for (a) k / a[i] or (b) a[i] - k, if found, return index j from permuted index array, Time O(log(n))
использовать nlog(n) для сортировки
, затем итерация по массиву
для каждого индекса i вычислить, каким должно быть A[j], чтобы уравнение было выполнено
проверяем, есть ли такое значение в массиве
O(nlogn) + O(N)*O(logn)
=O(nlogn)
Если k фиксировано, то существует конечное число целых чисел x, y таких, что x * y = k. Для каждого фактора (x, y) выполните итерацию по списку, чтобы определить, A [i] = x или A [i] = y. Общее время выполнения = O (n) * # факторов k = O (n) (детерминированно, а не предположения о хешировании)
Проблема утверждает, что все A [i] положительны, поэтому k можно разложить x + y = k конечным числом способов, так что и O (n).