Найти пару элементов массива с заданной суммой и произведением в O (n * log (n))

Question

Пусть A - массив из n натуральных чисел, и k - заданное целое число.

Я ищу алгоритм, чтобы найти, есть ли в массиве пара элементов, такая что A[i] * A[j] == k и A[i] == A[j] + k.Если такая пара существует, алгоритм должен вернуть их индекс.

Это домашнее задание, и нам говорят, что существует решение O (n * log (n)).

Answer 1

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))

Answer 2

Первое, что пришло мне в голову:

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 может быть лучше в лучшем случае, но хуже в худшем)

Answer 3

Вот несколько проясненное решение 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;
}

Answer 4

используйте nlog (n), чтобы отсортировать
, затем пройти через массив
для каждого индекса. Я вычисляю, каким должно быть A [j] для того, чтобы уравнение было выполнено
.в массиве есть такое значение

O (nlogn) + O (N) * O (logn)
= O (nlogn)

Answer 5

Если 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) также.