高效地找到一个不在大小为40、400或4000的集合中的整数。

Question

高效地找到一个不在大小为40、400或4000的集合中的整数。

29

与经典问题“在四十亿个数中找到一个不重复的整数”相关但不完全相同。为澄清，这里所说的整数实际上只是其数学定义的一个子集。也就是说，假设只有有限数量的整数。在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。

- aafulei

2

将向量排序可以在O(n log(n))的时间复杂度内完成，不确定是否能够得到更高效的算法。 - 463035818_is_not_a_number

3

向量是否已排序？对于集合来说，这是微不足道的，因为它是有序的。 - NathanOliver

1

@user463035818 如果你能在O(log(n))的时间复杂度内对一个向量进行排序，那你肯定会变得非常富有。 - Walter

2

@Walter 哎呀，这只是个打字错误，可惜我没有赚到百万。 - 463035818_is_not_a_number

2

排序完成后，您需要执行：Last + 1？ - JVApen

显示剩余13条评论

6个回答

10

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

如果我们想使用确定性方法，并且假设大小n不太大，例如4000，则我们可以创建一个大小为m = n + 1（或者稍微大一些，例如4096以便于计算）的向量x，并将其初始化为0。

对于每个范围中的i，我们只需设置x [array [i]模m] = 1。

然后，在x中进行简单的O（n）搜索将提供一个不在array中的值。

注意：模运算不是 "%" 运算符。

编辑：我提到选择4096的大小会使计算更加容易。更具体地说，这意味着模运算是通过简单的&运算执行的。

- Damien

6

如果您被允许重新排列输入向量，可以使用以下算法在O（N）时间内使用O（1）辅助空间找到最小未使用的整数。[注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）中的某个k，则现在它将出现在位置k。这种重新排列是通过交换来完成的，以避免丢失数据。一旦完成了该扫描，第一个值与其索引不同的条目将不会在数组中任何地方被引用。

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

要看到此算法的O（N）性质，应该观察到行6和7处的交换只能发生在目标条目不等于其索引的情况下，并且在交换后，目标条目等于其索引。因此，最多可以执行N次交换，并且线5处的if条件语句最多将N次为true。另一方面，如果if条件为false，则scan将增加，这也只能发生N次。因此，if语句最多评估2N次（即O（N））。

注： 1.我在这里使用无符号整数，因为它使代码更清晰。该算法可以轻松调整为有符号整数，例如通过将有符号整数从[INT_MIN，0）映射到无符号整数[INT_MAX，INT_MAX-INT_MIN）（减法是数学上的，而不是根据C语义的，这将不允许表示结果）。在2's-complement中，这是相同的位模式。当然，这会改变数字的顺序，这会影响“最小未使用整数”的语义；也可以使用保持顺序的映射。

- rici

为了满足OP的要求，只需处理最小的正未使用数即可，因此处理有符号整数的更简单的方法是如果数字为负数，则不进行交换。 - Taemyr

@taemyr：如果您使用负整数的“二进制补码”映射，就会发生这种情况，这不需要额外的测试（假设C中的强制转换是无操作）。一般来说，如果您想在某个范围内找到最小的可用数字，则可以忽略该范围之外的任何条目，并从有用的条目中减去该范围的开头。我本来想添加这个观察结果，但我更感兴趣的是原始算法的优雅程度。 - rici

4

生成一个随机数x（INT_MIN..INT_MAX），并对其进行测试。如果失败，则将x++进行测试（对于40/400/4000来说，这是非常罕见的情况）。

- Alexey Birukov

2

他正在寻找一种高效的方法来完成这个任务，这将是O(n^2)。是的，大多数情况下它会更好，但在最坏情况下仍然非常低效（而且OP特别要求O，这是针对最坏情况的）。 - dquijada

1

@dquijada 不是的。大O符号描述了一个函数的渐近行为，但这并不意味着它是任何东西的最坏情况。换句话说，一个算法可能有不同的上界，取决于你正在研究的输入。 - Acorn

2

通常情况下，我们使用大O符号表示算法的最坏时间复杂度，即对于所有输入数据而言所需的最长时间。当然，尽管某些输入数据可能需要更短的时间，但考虑到所有情况下的最坏时间复杂度是必要的。大O符号也可以用来描述平均情况的时间复杂度。然而，据我所知，“这个算法的时间复杂度为O(f(n))”这句话的默认意思是O(f(n))是指最坏情况，而非平均情况。 - Bakuriu

1

@Bakuriu 大O符号与分析的复杂性类型无关。它甚至可能不是时间复杂度。当然，你可以争论我们可能假设我们正在谈论最坏情况下的时间复杂度，但dquijada说“OP特别要求O，那就是最坏情况”，这根本不是真的。OP没有明确提到任何关于最坏情况的事情（相反：我们只能假设），也没有“O”表示最坏情况（这完全不正确）。 - Acorn

3

在这个特定的问题中，这种解决方案实际上在实践中非常高效，因为你几乎永远不会遇到最坏情况（或者如果你检测到可能会发生最坏情况，例如尝试了几次之后，你可以简单地回退到另一个解决方案；从而轻松地给你一个最坏情况为O(n)的算法）。因此，仅仅通过说它是O(n^2)并声称OP想要一个好的最坏情况算法来驳回这个解决方案是错误的。 - Acorn

显示剩余4条评论

2

步骤1：对向量进行排序。

可以使用O(n log(n))的算法完成，您可以在网上找到几种不同的算法，选择您最喜欢的一种。

步骤2：查找向量中第一个不是整数的数。

可以轻松地从INT_MIN到INT_MIN + 40/400/4000迭代，检查向量是否具有当前整数：

伪代码：

SIZE = 40|400|4000 // The one you are using
for (int i = 0; i < SIZE; i++) {
    if (array[i] != INT_MIN + i)
        return INT_MIN + i;

解决方案将是 O(n log(n) + n)，意思是：O(n log(n))。

编辑：刚刚看到您的编辑要求比O(n log(n))更好的东西，抱歉。

- dquijada

1

你可以使用二分查找算法在O(log N)时间复杂度内完成搜索。 - rici

1

@rici：如果你要二分查找“缺失的数字”，你会怎么做？如果你知道一个缺失的数字，你可以在log(n)时间内找到它在排序数组中所属的位置。我认为你不能做得比线性更好，尽管可能有较低的常数因子。对于均匀分布，线性搜索平均需要O(n / max_n)时间才能找到间隙，但最坏情况是n（直到最后没有间隙）。 - Peter Cordes

如果您使用选择排序进行排序，可以在运行时检查间隙，并且很有可能在第一次或第二次遍历中找到非重复项。（特别是如果您还检查了一个随机猜测的候选项。）对于小尺寸，O（n）符号不太有意义/有用。 - Peter Cordes

2

@peter：使用线性搜索的方式，将 i + min 与 vec[i] 进行比较。如果它们不相等，则在 i 之前存在缺失值，因此您需要进行二分查找；否则您需要进行上溯二分。二分查找适用于任何单调谓词。 - rici

@rici：啊，好的，这很有道理。但是如果你的数据一开始就没有排序，我认为你最好还是在排序过程中进行实时搜索，使用像QuickSort或RadixSort这样的分区或分组算法，这样你可以在完成整个排序之前可能在整个数组的子集中找到一个间隙，并确保缺失的值不会出现在其他任何地方。或者对于小数组，也许可以同时寻找最小值和最大值的SelectionSort，这样你通常可以很快获胜。你甚至不需要把排序后的值放在任何地方，只需要低/高计数器即可。 - Peter Cordes

显示剩余3条评论

0

如果提供的整数是在std::unordered_set<int>中（而不是std::vector<int>），您可以简单地遍历整数值的范围，直到找到一个不在unordered_set<int>中的整数值。在std::unordered_set<int>中搜索整数的存在性非常简单，因为std::unodered_set通过其find()成员函数提供了搜索功能。

这种方法的空间复杂度为O(1)。

如果您从 int 的最小可能值（即 std::numeric_limits<int>::min()）开始遍历，您将获得未包含在 std::unordered_set<int> 中的最小int 值：

int find_lowest_not_contained(const std::unordered_set<int>& set) {
   for (auto i = std::numeric_limits<int>::min(); ; ++i) {
      auto it = set.find(i); // search in set
      if (it == set.end()) // integer not in set?
         return *it;
   }
}

类比地，如果您从 int 的最大可能值（即 std::numeric_limits<int>::max()）开始遍历，则会得到未包含在 std::unordered_set<int> 中的最小 int 值。

int find_greatest_not_contained(const std::unordered_set<int>& set) {
   for (auto i = std::numeric_limits<int>::max(); ; --i) {
      auto it = set.find(i); // search in set
      if (it == set.end()) // integer not in set?
         return *it;
   }
}

假设哈希函数将整数（int）“均匀”映射到unordered_set的桶中，则可以在常量时间内完成对unordered_set的搜索操作。运行时复杂度将是O(M)，其中M是您正在寻找非包含值的整数范围的大小。 M由unordered_set的大小上限为界（即，在您的情况下，M <= 4000）。

实际上，采用此方法，选择任何大小大于unordered_set大小的整数范围，保证会遇到未出现在unordered_set中的整数值。

- JFMR

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Walter · Accepted Answer

你可以返回第一个不在输入中的 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.
 }

随机方法可能更节省空间，但在最坏情况下可能需要更多地遍历数据。