唯一元素数组的最小间隔

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).

实施细节

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

初始化:

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

现在在循环内部(从输入数组的末尾到输入数组的开始循环索引),

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

  只需检查您看到的整数,并更新索引上次看到的数组中的条目.

• 在最后看到的数组中使用之前和之后,更新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)