Получить произведение каждой пары в массиве

Question

У меня есть массив целых чисел, и я должен найти произведение каждой пары в массиве. Сказать массив {1,2,3,4}, тогда выход должен быть {1*2, 1*3, 1*4, 2*3, 2*4, 3*4}.

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

Answer 1

Если нет избыточности, нет другого способа, кроме выполнения умножения n*(n-1)/2.

Представьте себе график, в котором каждый элемент является узлом, и каждое ребро представляет собой умножение узлов.

Это результат полный график, и ваш результат является результатом каждого края, и вы получите n*(n-1)/2.

Answer 2

Вы не можете.

Поскольку у вас могут быть уникальные результаты O (n^2), вам нужны операции O (n^2) для доступа к каждому из этих чисел.

Например, возьмите случай, когда все числа в 2 массивах являются уникальными первичными числами.