произведение двух чисел в массиве

Question

Задан массив из n различных целых чисел.Найдите все пары x, y в массиве так, чтобы z (задано) = x * y ... делало это без сортировки и наиболее эффективным способом.

[edit] Целое число находится в диапазоне от intто есть 0-65536 и числа не отрицательные, если это помогает.Не хочу разбирать, потому что это займет много времени.Место для хранения не является проблемой.

Answer 1

Вот решение, основанное на линейном хэше:

Let hash be an array of size 65537 initilized to 0.

foreach element ele in Array

    if ele != 0
        hash[product/ele] = ele
    end-if

    if hash[ele] != 0 AND ele * hash[ele] == product
        print ele, product/ele
    end-if

end-foreach

Answer 2

Не существует супер-эффективных способов сделать это. Лучшее, о чем я могу думать, это O (n ^ 2):

Имеет вспомогательную функцию, которая принимает число (a) и список и проходит через каждый элемент (b), проверяя a * b = z и сохраняя пару, если она есть.

Просмотрите каждый элемент вашего исходного списка, и если определенный элемент (x) делит z (то есть z% x = 0), тогда отправьте x и остаток списка после x вспомогательной функции.

UPDATE:

Я даю решение O (n ^ 2), потому что в вопросе не указаны уникальные пары. Если нужны только уникальные пары, это следует добавить к вопросу. Кроме того, мое решение предполагает, что порядок пар не имеет значения, что является еще одной деталью, которую следует уточнить.

Answer 3

Итерация по массиву ... если элемент x может делить z (т.е. z % x == 0), проверьте, существует ли его другой фактор y=(z/x) в HashTable ....

Если это так, то вы нашли пару ... иначе просто добавьте ее в hashTable и продолжайте ...