c++ - 按照每对权重之和的顺序，高效地计算两个加权集合中的对

Question

假设我有两组数据，每个条目都包含一个权重。每组按重量升序排列。我将列出几个示例集:

Set 0: {4, 8, 19, 25, 25, 26}    
Set 1: {1, 2, 3, 8, 20, 27}

我想找到这两个集合之间的每一个可能的对，但我想按照它们的权重总和从小到大的顺序找到这些对。所以 4+1、4+2、4+3、8+1 等。你可以假设这些集合是 c++ std::multiset，但除此之外，我认为它在任何语言。

现在，我考虑使用 2 个迭代器，并从第一个迭代器开始按顺序与每秒配对，等等，但这不会按从最小总和权重开始的顺序计算每对，因为 Set 0: 4 + 设置 1: 8 > 设置 0: 8 + 设置 1: 1，在此示例中。我总是可以将结果转储到为我进行排序的容器中，但这似乎效率低下。我还有其他优化也取决于能否做到这一点。有没有一种聪明的方法可以做到这一点，而无需最后进行额外的排序？

编辑:我需要获得所有可能的配对，因此这并不像增加一个迭代器或另一个迭代器以获得最小总和那么简单。这将错过大多数(一半？)的对。虽然可能有某种迭代器堆栈......

Answer 1

让我们表示 2 个排序列表 A(大小 m)和 B(大小 n)。

算法:

1. 计算所有 i = 0 到 n - 1 的 A[0] 和 B[i] 的总和。您需要确定总和包含列表 A 中的哪个元素 - 一种方法是附上索引(此处所有总和均为 0)。将所有对插入按总和排序的最小堆中。
2. 弹出堆，并取出总和。使用附加的索引来计算与列表 A 中的下一个元素的总和。如果索引已经是 m - 1，则无需执行任何操作；否则增加索引并将其推回到堆中。
3. 重复步骤 2，直到堆为空(对于所有 m * n 值)。

第 1 步的时间复杂度为 O(n log n)。

第 2 步最多是 O(log n)，因为堆的大小可能会减小并且永远不会增加。重复步骤 2 m * n 次，时间复杂度为 O(mn log n)。

总体复杂度为 O(mn log n)。

通过使用较小的列表作为上面算法中的列表B，我们可以实现稍微好一点的时间复杂度(我们只需要管理一个小堆而不是一个大堆)。

使用 std::priority_queue 的实现(由 Stacker ):

#include <iostream>
#include <set>
#include <queue>
#include <limits>

std::multiset<int> set1 {4, 8, 19, 25, 25, 26};
std::multiset<int> set2 {1, 2, 3, 8, 20, 27};

struct Node
{
  Node(std::multiset<int>::const_iterator set1Iterator, int set2Value) :
    set1Iterator(set1Iterator),
    set2Value(set2Value),
    sum(*set1Iterator + set2Value)
  {
  }

  bool operator < (const Node& other) const
  {
    return sum > other.sum; // Reverse order as std::priority_queue sorts for the greatest value
  }

  std::multiset<int>::const_iterator set1Iterator;
  int set2Value;
  int sum;
};

int main()
{
  std::priority_queue<Node> heap;
  for (auto i = set2.begin(); i != set2.end(); ++i)
    heap.push(Node(set1.begin(), *i));

  while (!heap.empty())
  {
    Node min(heap.top());
    heap.pop();

    std::cout << *min.set1Iterator << " + " << min.set2Value << " = " <<
      min.sum << std::endl;
    if (++min.set1Iterator != set1.end())
    {
      min.sum = *min.set1Iterator + min.set2Value;
      heap.push(min);
    }
  }
  return 0;
}