0

我有 N 个数字可以说20 30 15 30 30 40 15 20。现在我想找出给定范围内有多少对数字。（给定L和R）。数字对=两个数字相同。我的做法：

创建一个数组映射，使得map 的键= 数字，值= 出现该数字的索引的数组列表。然后我从 L 遍历到 R 并且对于该范围内的每个值，我在相应的数组列表中遍历以查找是否有一对适合范围，然后增加计数。

但我认为这种方法太慢了。有没有更快的方法来做同样的事情？

示例：对于上述给定序列，L=0 和 R=6 答案=5。可能的配对是 20 的 1、15 的 1 和 30 的 3。

我正在开发一个解决方案，假设数字可以达到 10^8（并且非负数）。

4

2 回答 2

0

如果您正在寻找速度并且不关心内存，那么可能有更好的方法。

您可以使用集合作为辅助数据结构来查看是否找到了数字，然后简单地遍历数组。伪代码：

int numPairs = 0;
set setVisited;
for (int i = L; i < R; i++) {
  if (setVisited.contains(a[i])) {
    // found the second of a pair. count it up and reset.
    numPairs++;
    setVisited.remove(a[i]);
  } else {
    // remember that we saw this number, so we can spot the next pair.
    setVisited.add(a[i]);
}
于 2015-05-16T17:17:58.890 回答
0

新的解决方案......希望这次会更好。伪 C-ish 代码：

// Sort the sub-array a[L..R]. This can be done O(nlogn) using qsort.
// ... code omitted ...

// Walk through the sorted array counting how many times number occurs.
// When the number changes, count how many possibles ways to make pairs
// from the given count.
int totalPairs = 0;
int count = 1;
int current = a[L];
for (i = L+1; i < R; i++) {
  if (a[i] == current) { // found another, keep counting
    count++;
  } else { // found a different one
    if (count > 1) { // need at least 2 to make a pair!
      totalPairs += factorial(count) / 2;
    }
  }
  // start counting the new one
  current = a[i];
  count = 1;
}

// count the final one
if (count > 1) {
  totalPairs += factorial(count) / 2;
}

排序运行 O(nlgn)，循环体运行 O(n)。有趣的是，性能障碍现在是因子。对于出现次数非常多的非常长的数组，除非您进一步优化，否则阶乘是昂贵的。

一种方法是循环计数重复但不计算阶乘——留下另一个数字计数数组。然后对该数组进行排序（再次为 Nlg(N)），然后遍历该数组并重新使用先前计算的阶乘来计算下一个。

此外，如果这个数组变大，您将需要一个大整数来表示总数。我不知道大整数的 O() 性能。

很酷的问题！

于 2015-05-16T21:12:14.307 回答