正の整数を含む2つの配列（重複を含むことができ、同じ長さである可能性があります）が与えられます。両方の配列から数値を1回しか使用できない場合、絶対差が特定の値（指定された値）に等しくないペアの最大数を見つける必要があります。
例えば：
arr1 = {1,2,3,4}
arr2 = {8,9,10,11}
diff = 5
次に、可能なペアは（3,8）、（4,8）です。つまり、そのような可能なペアは2つだけです。
出力は2である必要があります。
また、O（n ^ 2）でこれのアルゴリズムを考えることができます。しかし、もっと良いものが必要です。ハッシュマップ（配列に重複が含まれているため機能しません）を考え、配列を降順と昇順で並べ替えることを考えましたが、そこから先に進むことはできませんでした。
通常の考え方は、ソートされた範囲をループすることです。これにより、力ずくのO(N^2)努力を通常に下げることができますO(N log N)。
疑似コードでのそのためのアルゴリズムは次のとおりです（後で実際のC ++コードで更新する可能性があります）。
全体として、これは平均してかかる種類によって支配されますO(N log N)。
約束されたコードは次のとおりです。
auto find_pairs(std::vector<int>& arr1, std::vector<int>& arr2, int diff)
{
std::vector<std::pair<int,int> > ret;
std::sort(std::begin(arr1), std::end(arr1));
std::sort(std::begin(arr2), std::end(arr2));
auto it1= std::begin(arr1);
auto it2= std::begin(arr2);
while(it1!= std::end(arr1) && it2!= std::end(arr2))
{
if(std::abs(*it1-*it2) == diff)
{
ret.push_back(std::make_pair(*it1,*it2));
++it1;
++it2;
}
else if(*it1<*it2)
{
++it1;
}
else
{
++it2;
}
}
return ret;
}
2つのベクトルの一致する要素をのベクトルとして返しますstd::pairs。あなたの例では、それは印刷します
3 8
4 9
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加