如何找到具有差小于一个特定值对的最大数目？ [英] How to find the maximum number of pairs having difference less than a particular value?

问题描述

我给出两个数组（可以包含重复与相同长度的）含正整数。我已经发现，具有一个特定值（定）绝对差小于等于对的最大数目时，数字可以同时从阵列中只能使用一次。

例如：

  ARR1 = {1,2,3,4}
ARR2 = {8,9,10,11}
差异= 5
 

然后，可以对为（3,8），（4,8）。也就是说，只有两个这样可能对在那里。

输出应为2。

另外，我能想到的算法中的这为O（n ^ 2）。但是，我需要更好的东西。我想到了哈希映射（将无法工作，因为数组包含重复），在下降和上升的顺序排序数组的想法，是不是真的能够从那里前进。

解决方案

通常的想法是遍历的排序的范围。这一点，你可以打倒蛮力 O（N ^ 2）努力通常 O（N日志N）。

下面是一个算法，在伪code（也许我以后会​​与真正的C ++ code更新）：

• 排序两个数组
• 在遍历双方同时与两个迭代器：
  1. 如果一对被发现将其插入到你的列表中。同时增加的迭代器。
  2. 否则，增加指标指向更小的元素。

在总，这是由它的平均花费 0排序为主（N​​日志N）。

---

下面是承诺code：

 自动find_pairs（标准::矢量＆lt; INT＆GT;＆安培; ARR1，性病::矢量＆lt; INT＆GT;＆安培; ARR2，诠释DIFF）
{
    的std ::矢量＆lt;的std ::对＆LT; INT，INT＆GT; ＆GT; RET;

    的std ::排序（STD ::开始（ARR1），性病::端（ARR1））;
    的std ::排序（STD ::开始（ARR2），性病::端（ARR2））;

    汽车IT1 =的std ::开始（ARR1）;
    汽车IT2 =的std ::开始（ARR2）;

    而（IT1 =的std ::结束（ARR1）及！＆安培;！IT2 =的std ::结束（ARR2））
    {
        如果（STD :: ABS（* it1- * IT2）==差异）
        {
            ret.push_back（的std :: make_pair（* IT1，* IT2））;
            ++ IT1;
            ++ IT2;
        }
        否则，如果（* IT1＆LT; * IT2）
        {
            ++ IT1;
        }
        其他
        {
            ++ IT2;
        }
    }

    返回RET;
}
 

它返回两个向量的匹配元素为的载体的std ::对。对于您的例子，它打印

  3 8
4 9
 

演示

I am given two arrays (can contain duplicates and of same length) containing positive integers. I have to find the maximum number of pairs that have absolute difference less than equal to a particular value (given) when numbers can be used only once from both the arrays.

For example:

arr1 = {1,2,3,4}
arr2 = {8,9,10,11}
diff = 5

Then, possible pairs are (3,8), (4,8). That is, only two such possible pairs are there.

Output should be 2.

Also, I can think of an algo for this in O(n^2). But, I need something better. I thought of hash maps (won't work because arrays contain duplicates), thought of sorting the arrays in descending and ascending order, wasn't really able to move forward from there.

解决方案

The usual idea is to loop over sorted ranges. This, you can bring down the brute-force O(N^2) effort to usually O(N log N).

Here is an algorithm for that in pseudo code (maybe I'll update later with real C++ code):

• Sort both arrays
• Loop over both simultaneously with two iterators:
  1. If a pair is found insert it into your list. Increase both iterators.
  2. Otherwise, increase the indicator pointing to the smaller element.

In total, this is dominated by the sort which on average takes O(N log N).

---

Here is the promised code:

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;
}

It returns the matching elements of the two vectors as a vector of std::pairs. For your example, it prints

3  8
4  9

DEMO

这篇关于如何找到具有差小于一个特定值对的最大数目？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！