algorithm - 唯一元素数组的最小间隔

Question

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

Answer 1

策略是从头到尾迭代，记住你最后一次看到每个整数的时间。例如。在中间的某个地方，您最后一次在索引 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) .

---

实现细节

实现这个需要一些工作。

初始化:

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

现在进入循环(从输入数组末尾到输入数组开头的循环索引)，

• 您可以为这个特定索引更新您最后一次看到的数组。

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

• 在最后一次看到的数组中使用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)