在两个数组中搜索三元组

Question

给出大小为n的两个数组a和b。我必须从a中选择一个元素，然后从b中选择两个元素。 a[i] * a[i] = b[j] * b[k]。

我能够在O(n^2 log(n))中找到遍历数组和二进制搜索值的BruteForce。但是不知道如何进一步改善它。

如何计算元素在1 <= a[i] <= 10^6和1 <= n <= 10^6之间的所有这些数字。

Answer 1

的O（n ^ 2 log（n）））中找到BruteForce

嗯，我可以考虑一个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
            }
        }
    }
}
这里您遍历两个数组。主要目标是针对b中的每个元素检查必须与哪些元素相乘才能等于a的某个元素平方。 ，它检查B所需的元素是否已经在S中。

其中有一个小技巧。如果A = 30和B = 30，则表示您想在b中再增加一个30，而不是B。这就是多重​​集合的原因。如果整个集合中只有30个，则您知道您正在尝试将B与自身进行匹配，而您不能这样做，因此必须在b中至少包含2个值30的元素。 >