3

给定一个长序列的 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

任何帮助，将不胜感激。

4

4 回答 4

5

保留两个哈希值，一个映射数字到它们出现的最小位置，一个映射数字到它们出现的最大位置。如果 minimum[a] < great[b] （并且两个哈希键都存在），则有序对 (a, b) 按顺序出现。预处理时间是线性的，空间使用是线性的，查询时间是恒定的（在关于散列复杂性的标准假设下）。

至于计数版本，我能想到的最好的方法是保持一个哈希将每个数字映射到它按排序顺序出现的位置。要查询一对，“合并”位置列表，跟踪到目前为止 a 元素的数量和对出现的数量。When a b-element is selected to be next, increment the number of pairs by the number of a-elements. When an a-element is selected to be next, increment the number of a-elements. （如果 a == b，返回长度选择 2。）

于 2012-06-01T17:14:37.117 回答
1

这是一个 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));
}
于 2012-06-01T17:14:07.097 回答
1

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

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

改进思路：

  • 您可以将 aDictionary<int, List<Pair>>用于对的列表。
  • 您可以在对中放置一个活动计数，因此您无需在活动列表中添加另一个引用，而是增加活动计数。
于 2012-06-01T17:26:39.967 回答
-2

假设所有数字都不同，您不认为蛮力解决方案是唯一的解决方案。

于 2012-06-01T17:10:32.757 回答