检测长列表中出现的成对元素的算法

Question

给定一个长度为N（不一定不同）的数字序列，例如

{1, 50, 3, 99, 1, 2, 100, 99, 4, 100, 4, 100} (could be very long)

还有一小组M个有序对，比如说

(1, 2)

(2, 1)

(1, 3)    

(99, 50)

(99, 100)

我希望能够检测出有序对是否在列表中任何位置出现（它们可以分开，但是顺序很重要）。例如，上面的计数将是：

(1, 2): 2 (each 1 pairs with the later 2)

(2, 1): 0 (no 1's come after the 2)

(1, 3): 1 (only one of the 1's come before the 3)

(99, 50): 0 (no 99's come before the 50)

(99, 100): 5 (3 times for the first 99 and 2 times for the second)

假设有序对中的每个数字都保证出现在列表中，是否存在一种比朴素的O（N * M）时间更快的算法来提取这些计数？作为一个副问题，如果我们限制自己只考虑布尔值而不是计数，是否可能存在快速算法？也就是说：

(1, 2): yes

(2, 1): no

(1, 3): yes

(99, 50): no

(99, 100): yes

非常感谢您的帮助。

- donnyton

---

限制自己只使用布尔值可能会有很大的帮助——考虑一种极端情况，即你要查找的所有配对都在人口中首先出现。 - 500 - Internal Server Error

Answer 1

保留两个哈希表，一个映射数字到其出现的最小位置，另一个映射数字到其出现的最大位置。如果least[a] < greatest[b]（并且两个哈希键都存在），则有序对（a，b）按顺序显示。预处理时间为线性，空间使用量为线性，查询时间为常数（在哈希复杂度的标准假设下）。

至于计数版本，我能想到的最好方法是保留一个哈希表，将每个数字映射到按排序顺序出现的位置。要查询一个配对，“合并”位置列表，跟踪a元素数量和配对出现次数。当选择下一个b元素时，将配对数量增加a元素数量。当选择下一个a元素时，递增a元素数量。（如果a == b，则返回长度选取2）。

- Chris

---

那么澄清一下，映射步骤需要O(N)的时间，不会触及到这些对，完成后我们总共需要O(N+M)的时间来查找每个对吗？而对于计数，你的算法仍然是O(N*M)，因为合并步骤可能需要O(N)的时间。 - donnyton

Answer 2

这里有一个O(n)的解决方案...

unordered_map<int, unordered_set<int>> pairs = ...;

void process(int n)
{
    // keep list of pairs that have their first seen, indexed by second...
    static unordered_map<int, vector<pair<int,int>>> live;

    // if next item is in live list, we have found some pairs...
    for (auto found_pair : live[n])
        process(found_pair);

    // add pairs to live list that have a first of the current item
    for (auto pair : pairs[n])
        for (auto second : pair.second)
           live.insert(second, make_pair(pair.first, second));
}

- Andrew Tomazos

---

我会建议创建一个表格，将第一对映射到第二对，然后再建立另一个以你所寻找的第二对为键的表格。 - Vatine

我原以为他对连续的一对感兴趣。重新阅读问题后，它看起来更加复杂。 - Andrew Tomazos

Answer 3

您可以保留一个活动对列表，并循环遍历数字列表。每当您找到一对的第一个数字时，将该对复制到活动列表中。每当您在活动列表中找到一对的第二个数字时，就会增加该对的计数。

C#示例：

public class Pair {

  public int First { get; private set; }
  public int Second { get; private set; }
  public int Count { get; set; }

  public Pair(int first, int second) {
    First = first;
    Second = second;
    Count = 0;
  }

}

int[] values = {1, 50, 3, 99, 1, 2, 100, 99, 4, 100, 4, 100};

List<Pair> pairs = new List<Pair>();
pairs.Add(new Pair(1, 2));
pairs.Add(new Pair(2, 1));
pairs.Add(new Pair(1, 3));
pairs.Add(new Pair(99, 50));
pairs.Add(new Pair(99, 100));

List<Pair> active = new List<Pair>();

foreach (int value in values) {
  foreach (Pair p in active) {
    if (p.Second == value) {
      p.Count++;
    }
  }
  foreach (Pair p in pairs) {
    if (p.First == value) {
      active.Add(p);
    }
  }
}

foreach (Pair p in pairs) {
  Console.WriteLine("({0},{1}) : Count: {2}", p.First, p.Second, p.Count);
}

输出：

(1,2) : Count: 2
(2,1) : Count: 0
(1,3) : Count: 1
(99,50) : Count: 0
(99,100) : Count: 5

改进想法：

• 您可以使用 Dictionary<int, List<Pair>> 来存储成对的列表。
• 您可以在成对中添加一个活动计数，这样，您就不需要在活动列表中添加另一个引用，而是增加活动计数。

- Guffa

Answer 4

假设所有数字都不同，你不觉得暴力解决方案是唯一的解决方案吗？

- HBY4PI

---

你有什么依据来做这个声明？对列表进行排序并保留原始索引指针，对于每一对检查索引。复杂度为O((N+M)logN)。 - davin

哦，我以为如果所有数字都不同，那么就会有O（NM）对，因此提取这些对至少需要O（NM）操作。当然，找到特定对出现的次数是完全不同的。 - HBY4PI

@davin 你应该把你的评论写成一个答案。 - Facundo Casco

@F.C.，你可以拥有它。享受吧！ - davin

对列表进行排序将重新排列元素，因此我们将无法区分对(1,2)和(2,1)。我认为排序不能帮助解决这个问题。 - fdermishin