有效地找到不在大小为40,400或4000的整数中的整数

Question

与经典问题相关的是找到一个不在40亿个给定值中但不完全相同的整数.

为了澄清,通过整数我真正的意思只是其数学定义的一个子集.也就是说,假设只有有限数量的整数.用C++说,它们int在范围内[INT_MIN, INT_MAX].

现在给出一个std::vector<int>(没有重复)或者std::unordered_set<int>其大小可以是40,400,4000左右,但不是太大,如何有效地生成一个保证不属于给定数字的数字？

如果不担心溢出,那么我可以将所有非零的相加,并将产品加1.但是有.对手测试用例可以包含INT_MAX.

我更赞成简单,非随机的方法.有没有？

谢谢!

更新:为了消除歧义,让我们说一个未分类的std::vector<int>,保证没有重复.所以我问是否有比O(n log(n))更好的东西.另请注意,测试用例可能包含INT_MIN和INT_MAX.

Answer 1

您可以只返回N+1输入中未包含的第一个候选整数.最简单的候选人人数0来N.这需要O(N)空间和时间.

 int find_not_contained(container<int> const&data)
 {
     const int N=data.size();
     std::vector<char> known(N+1, 0);   // one more candidates than data
     for(int i=0; i< N; ++i)
         if(data[i]>=0 && data[i]<=N)
             known[data[i]]=1;
     for(int i=0; i<=N; ++i)
         if(!known[i])
             return i;
     assert(false);                     // should never be reached.
 }

随机方法可以更节省空间,但在最坏的情况下可能需要更多的数据传递.

Answer 2

随机方法在这里确实非常有效.

如果我们想要使用确定性方法并假设大小n不是太大,例如4000,那么我们可以创建一个大小的矢量xm = n + 1(或者稍微大一点,例如4096以便于计算),初始化为0 .

对于i范围内的每一个,我们只设置x [array [i] modulo m] = 1.

然后在x中进行简单的O(n)搜索将提供不在数组中的值

注意:模运算不完全是"%"运算

编辑:我提到通过在这里选择4096的大小来简化计算.更具体地说,这意味着模运算是通过简单的&操作来执行的

Answer 3

如果允许使用以下算法重新排序输入向量,则可以使用O(1)辅助空间在O(N)时间内找到最小的未使用整数.[注1](如果向量包含重复数据,该算法也有效.)

size_t smallest_unused(std::vector<unsigned>& data) {
  size_t N = data.size(), scan = 0;
  while (scan < N) {
    auto other = data[scan];
    if (other < scan && data[other] != other) {
      data[scan] = data[other];
      data[other] = other;
    }
    else
      ++scan;
  }
  for (scan = 0; scan < N && data[scan] == scan; ++scan) { }
  return scan;
}

第一遍确保如果在位置之后找到k范围内的某些,则它现在位于位置.这种重新安排是通过交换来完成的,以避免丢失数据.扫描完成后,其值与索引值不同的第一个条目不会在数组中的任何位置引用.[0, N)kk

该断言可能不是100%明显,因为可以从较早的索引引用条目.但是,在这种情况下,条目不能是与其索引不相等的第一个条目,因为较早的条目将满足该条件.

要看到此算法为O(N),应该观察到第6行和第7行的交换只能在目标条目不等于其索引时发生,并且在交换后目标条目等于其索引.因此,最多N可以执行交换,并且第if5行的条件将是true最N多次.另一方面,如果if条件为假,scan则将递增,这也可能只发生N一次.因此,if语句在大多数2N时候被评估(即O(N)).

笔记:

1. 我在这里使用无符号整数,因为它使代码更清晰.可以很容易地对有符号整数调整算法,例如通过将有符号整数映射[INT_MIN, 0)到无符号整数[INT_MAX, INT_MAX - INT_MIN)(减法是数学的,而不是根据不允许表示结果的C语义.)在2的补码中,这是相同的位模式.当然,这会改变数字的顺序,这会影响"最小的未使用整数"的语义; 也可以使用保持顺序的映射.