algorithm - 找出非负整数序列中缺失的最小元素

Question

我需要从一个非负整数序列中找到最小缺失元素。

例如:我有:0 5 10 4 3 1

The missing element is 2.

在上面的序列中缺失的元素是 2 6 7 8 9 。其中最小的是 2，所以答案是 2。

蛮力。我将对序列进行排序并获得 nlogn 中的最小元素。我正在寻找更好的解决方案。有什么帮助吗？

Answer 1

在 ISO C99 中:

unsigned least_absent(unsigned seq_sz, unsigned seq[seq_sz])
{
   bool tab[seq_sz];
   memset(tab, 0, sizeof(tab));
   for(unsigned i=0; i<seq_sz; i++)
      if(seq[i] < seq_sz)
         tab[seq[i]] = true;
   for(unsigned i=0; i<seq_sz; i++)
      if(!tab[i])
         return i;
   return seq_sz;
}

这是 O(n) 时间，O(n) 内存。