时间戳

首页 > 解决方案 > 有效地找到不在大小为 40、400 或 4000 的集合中的整数

c++ - 有效地找到不在大小为 40、400 或 4000 的集合中的整数

问题描述

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

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

现在给定一个std::vector<int>（不重复） or std::unordered_set<int>，其大小可以是 40、400、4000 左右，但不能太大，如何有效地生成一个保证不在给定数字中的数字？

如果不担心溢出，那么我可以将所有非零值相乘并将乘积加 1。但是有。对手的测试用例可以故意包含INT_MAX.

我更赞成简单的、非随机的方法。有没有？

谢谢！

更新：为了消除歧义，假设一个未排序的std::vector<int>，保证没有重复。所以我问是否有比 O(n log(n)) 更好的东西。另请注意，测试用例可能同时包含INT_MIN和INT_MAX。

标签： c++algorithm

解决方案

您可以只返回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.
 }

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

推荐阅读