在数组O（n）中找到一对相等的整数吗？ [英] Is finding a pair of equal integers in an array O(n)?

问题描述

给出一个整数数组，最差的时间复杂度是什么，它会找到一对相同的整数？

Given an array of integers what is the worst case time complexity that would find pair of integers which are same ?

我认为这可以在O（n ），方法是使用计数排序或XOR。
我说得对吗？

I think this can be done in O(n) by using counting sort or by using XOR . Am i right ?

问题不担心空间的复杂性，答案是O（nlgn）。

推荐答案

计数排序

如果输入内容允许您使用计数排序，那么您要做的就是在O（n）时间内对输入数组进行排序，然后也在O（n）时间内查找重复项。由于实际上不需要对数组进行排序，因此可以改进该算法（尽管不算复杂）。您可以创建用于计数排序的相同辅助数组，该数组由输入整数索引，然后将这些整数一一添加，直到已经插入当前整数为止。此时，已经找到两个相等的整数。

If the input allows you to use counting sort, then all you have to do is sort the input array in O(n) time and then look for duplicates, also in O(n) time. This algorithm can be improved (although not in complexity), since you don't actually need to sort the array. You can create the same auxiliary array that counting sort uses, which is indexed by the input integers, and then add these integers one by one until the current one has already been inserted. At this point, the two equal integers have been found.

该解决方案提供了最坏情况，平均情况和最佳情况下的线性时间复杂度（ O（n） ），但要求输入整数必须在理想的范围内。

This solution provides worst-case, average and best-case linear time complexities (O(n)), but requires the input integers to be in a known and ideally small range.

散列

如果您不能使用计数排序，则可以使用哈希表，而不是使用辅助表，而是使用哈希表并使用与以前相同的解决方案（不进行排序）数组。哈希表的问题在于，它们的操作在最坏情况下的时间复杂度是线性的，而不是恒定的。确实，由于冲突和重新哈希处理，在最坏的情况下，插入是在O（n）时间内完成的。

If you cannot use counting sort, then you could fall back on hashing and use the same solution as before (without sorting), with a hash table instead of the auxiliary array. The issue with hash tables is that the worst-case time complexity of their operations is linear, not constant. Indeed, due to collisions and rehashing, insertions are done in O(n) time in the worst case.

由于您需要O（n）插入，因此最糟糕的情况是该解决方案的时间复杂度是二次（ O（n²）），即使其平均时间和最佳情况时间复杂度是线性的（ O（n））。

Since you need O(n) insertions, that makes the worst-case time complexity of this solution quadratic (O(n²)), even though its average and best-case time complexities are linear (O(n)).

排序

另一种解决方案是使用计数排序不适用的情况另一种排序算法。对于基于比较的排序算法，最坏情况下的时间复杂度充其量为O（n log n）。解决方案是对输入数组进行排序，并查找O（n）时间中的重复项。

Another solution, in case counting sort is not applicable, is to use another sorting algorithm. The worst-case time complexity for comparison-based sorting algorithms is, at best, O(n log n). The solution would be to sort the input array and look for duplicates in O(n) time.

此解决方案的最坏情况和平均时间复杂度为 O （n log n），并根据排序算法，确定最佳情况下的线性时间复杂度（ O（n））。

This solution has worst-case and average time complexities of O(n log n), and depending on the sorting algorithm, a best-case linear time complexity (O(n)).

这篇关于在数组O（n）中找到一对相等的整数吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！