arrays - 在 O(n) 数组中找到一对相等的整数？

Question

给定一个整数数组，找到一对相同的整数的最坏情况时间复杂度是多少？

我认为这可以通过使用计数排序或使用 XOR 在 O(n) 中完成。我说得对吗？

问题不担心空间复杂度，答案是 O(nlgn)。

Answer 1

计数排序

如果输入允许您使用计数排序，那么您所要做的就是在 O(n) 时间内对输入数组进行排序，然后查找重复项，同样在 O(n) 时间内。这个算法可以改进(虽然不复杂)，因为你实际上不需要对数组进行排序。您可以创建与计数排序相同的辅助数组，它由输入整数作为索引，然后将这些整数一个一个地相加，直到当前的那个已经被插入。至此，两个相等的整数已经求出。

此解决方案提供了最坏情况、平均情况和最佳情况的线性时间复杂度 (O(n))，但要求输入整数在已知且理想情况下较小的范围内.

散列

如果您不能使用计数排序，那么您可以退回到哈希并使用与以前相同的解决方案(不排序)，使用哈希表而不是辅助数组。哈希表的问题在于，它们操作的最坏情况时间复杂度是线性的，而不是恒定的。事实上，由于冲突和重新散列，在最坏的情况下，插入在 O(n) 时间内完成。

由于您需要 O(n) 次插入，这使得该解决方案的最坏情况时间复杂度为二次 (O(n²))，即使其平均时间复杂度和最佳情况时间复杂度是线性的(O(n))。

排序

如果计数排序不适用，另一种解决方案是使用另一种排序算法。基于比较的排序算法的最坏情况时间复杂度最多为 O(n log n)。解决方案是对输入数组进行排序并在 O(n) 时间内查找重复项。

此解决方案的最坏情况和平均时间复杂度为 O(n log n)，根据排序算法，最佳情况的线性时间复杂度 (O(n) ).