3

我怎样才能找到一个整数数组的最小间隔，其中该数组的所有唯一元素都存在。例如，我的数组是：1 1 1 2 3 1 1 4 3 3 3 2 1 2 2 4 1 最小间隔是从索引 3 到索引 7。我正在寻找 O(nlogn) 或更小的算法（n< =100000)

4

1 回答 1

6

该策略从结尾迭代到开头，记住您上次看到每个整数的时间。例如。在中间的某个地方，您最后在索引 15 处看到 1，在索引 20 处看到 2，在索引 17 处看到 3。间隔长度是您上次看到的最大索引减去当前索引。

为了轻松找到最大索引，您应该使用自平衡二叉搜索树 (BST)，因为它具有O(log n)插入和删除时间，以及最大索引的恒定查找时间。

例如，如果您必须更新上次看到的索引 1，则删除当前上次看到的索引（15），并插入新的上次看到的索引。

通过使用每个整数类型允许的所有结束索引更新自平衡 BST，我们可以选择最大的，并说我们可以在那里结束。

确切的代码取决于输入的定义方式（例如，您是否知道所有整数是什么，即您知道数组中存在 1 到 4 之间的所有整数，然后简化代码）。

迭代是O(n)，BST是O(log n)。总体来说是O(n log n)。

实施细节

实现这一点需要一些工作。

初始化：

  • 每个起始索引的间隔长度。
  • 上次看到某个整数时的数组。（如果您不知道数组中可能有哪些整数，请使用关联数组（例如，map<>在 C++ 中），而不是使用普通数组）。
  • 类似优先级队列的类型堆，其中队列的顶部是其中的最大整数。您需要能够轻松地从中删除内容，因此请使用自平衡二叉搜索树

现在在循环内部（从输入数组末尾到输入数组开头的循环索引），

  • 您可以为此特定索引更新您上次看到的数组。

    只需检查您看到的整数，然后更新索引最后一次看到的数组中的条目。

  • 在最后看到的数组中使用 before 和 after，更新 BST（删除旧的结束索引，添加新索引）

  • 根据所需的最大结束索引（来自 BST）更新此起始索引的间隔长度。

  • 如果您看到一个以前从未见过的整数，则使高于该索引的起始索引的所有间隔长度无效（或者只是避免更新间隔长度，直到所有整数至少被看到一次）。

C++代码实现

  • 假设在输入数组中找到所有整数 0-(k-1)
  • 免责声明：未经测试
  • 忽略#include和main功能

代码：

int n=10,k=3;
int input[n]=?;
unsigned int interval[n];
for (int i=0;i<n;i++) interval[i]=-1; // initialize interval to very large number
int lastseen[k];
for (int i=0;i<k;i++) lastseen[i]=-1; // initialize lastseen
multiset<int> pq;

for (int i=n-1;i>=0;i--) {
  if (lastseen[input[i]] != -1) // if lastseen[] already has index
    pq.erase(pq.find(lastseen[input[i]])); // erase single copy
  lastseen[input[i]]=i; // update last seen
  pq.insert(i); // put last seen index into BST
  if (pq.size()==k) { // if all integers seen (nothing missing)
    // get (maximum of endindex requirements) - current index
    interval[i] = (*pq.rbegin())-i+1;
  }
}
// find best answer
unsigned int minlength=-1;
int startindex;
for (int i=0;i<n;i++) {
  if (minlength>interval[i]) { // better answer?
    minlength=interval[i];
    startindex=i;
  }
}
// Your answer is [startindex,startindex+minlength)
于 2012-09-03T05:32:20.227 回答