Поиск триплетов в двух массивах

Question

Даны два массива a и b размером n. Я должен выбрать один элемент из a и два элемента из b, чтобы. a[i] * a[i] = b[j] * b[k].

Я могу найти BruteForce в O(n^2 log(n)), пересекающем как массивы, так и двоичные файлы, ищущие значение. Но не знаю, как улучшить его еще больше.

Как мне посчитать все эти числа, где элементы варьируются от 1 <= a[i] <= 10^6 и 1 <= n <= 10^6.

Answer 1

Ну, я могу подумать о решении O (n²).

unordered_multiset S = {}
for each element B in b {
    S = S ∪ B
}

Прежде всего, мы храним все элементы b в unordered_multiset. Такая структура может найти элементы за O (1) времени, и если вы добавите 2 или более равных элемента, она также знает.

for each element B in b {
    for each element A in a {
        if( A² % B != 0 ) continue;                            //making sure it's divisible
        let occurrencies = number_of_occurrencies(A² / B, S);
        if( occurrencies > 0 ) {                               //if (A² / B) is in S
            if( A == B and ocurrencies > 1 ) {
                //your answer is A, B and B
            }
            else if ( A != B ) {
                //your answer is A, B and A² / B
            }
        }
    }
}

Здесь вы l oop по обоим массивам. Основная цель - проверить, для каждого элемента в b, на какие элементы он должен быть умножен, чтобы быть равным некоторому элементу a в квадрате. Он проверяет, находится ли необходимый элемент B в S.

В этом есть небольшая хитрость. Если A = 30 и B = 30, это означает, что вы хотите иметь еще 30 в b, которые не B. Это причина мультимножества. Если во всем наборе есть только один 30, вы знаете, что пытаетесь сопоставить B с самим собой, и вы не можете этого сделать, поэтому вам нужно иметь как минимум 2 элемента со значением 30 в b.