您将得到n个整数的排序的数组，你想了解是否有阵列中的任何重复（即任意整数出现一次以上）。 该算法是基于对大小为n的整数无序阵列。使用嵌套循环的执行，以查找重复和复杂性; O（N ^ 2）

You are given an unsorted array of n integers, and you would like to find if there are any duplicates in the array (i.e. any integer appearing more than once). The Algorithm is based on unsorted array of size n integers. Use of nested loop was implemented to find duplicates and the complexity is; O (N^2)

如果我们限制输入数据，以实现一些最好的情况下，怎么能限制输入数据，以达到更好的大O的复杂性？描述一个算法来处理这​​有限的数据，以寻找是否有任何重复。什么是大O的复杂性？

该问题要求如下：

的数据如何被限制的一种方式。

one way of how the data can be limited.

这怎么改变你的算法找出重复的，什么是更好的大O的复杂性。

How this changes your algorithm for finding duplicates, and what is the better Big O complexity.

我想出了答案：

如果我们限制这些数据，让我们说，数组大小为5（N = 5），我们可以降低复杂度为O（N）。 如果数组排序，不是我们需要的是一个循环的每个元素比较下一个元素数组中，这将寻找是否存在重复。 它只是意味着，如果给我们一个数组是默认（或幸运）已经排序（从最低到最高值），在这种情况下，将减少从O（N ^ 2）O（N），因为我们不需要的内循环，用于比较整数用于排序，因为它已经排序因此我们可以实现一个单回路的整数比较其后继并且如果一个重复遇到，那么我们就可以，例如，使用一个printf语句打印重复并继续重复循环N-1次（这将是4） - 结束程序一旦已经完成。

If we limit the data to, let’s say, array size of 5 (n = 5), we could reduce the complexity to O(N). If the array is sorted, than all we need is a single loop to compare each element to the next element in the array and this will find if duplicates exist. Which simply means that if an array given to us is by default (or luckily) already sorted (from lowest to highest value) in this case the reduction will be from O(N^2) to O(N) as we wouldn’t need the inner loop for comparing the integers for sorting since it is already sorted therefore we could implement a single loop to compare the integers to its successor and if a duplicate is encountered, then we could, for instance, use a printf statement to print the duplicates and proceed to iterate the loop n-1 times (which would be 4)- ending the program once that has been done.

这个算法中的最好情况是O（N），只是因为性能线性和正比于输入的规模的增长/数据，所以，如果我们有大小50的有序数组（50整数数组中）然后迭代将n-1个（循环将重复50 - 1次），其中n是阵列的长度为50。 该算法在运行时间增加成正比的输入大小。这只是意味着在排序后的数组，时间的操作用来执行量完全取决于该阵列的输入大小。

The best case in this algorithm would be O(N) simply because the performance grows linearly and in direct proportion to the size of the input/ data so if we have a sorted array of size 50 (50 integers in the array) then the iteration would be n-1 (the loop will iterate 50 – 1 times) where n is the length of the array which is 50. The running time in this algorithm increases in direct proportion to the input size. This simply means that in a sorted array, the amount of time the operations take to perform is completely dependent on the input size of the array.

您确认（这是否是正确与否）将不胜感激。我知道还有其他的算法具有较好的复杂类，但因为这是为O更有效（N ^ 2），这将是一个可能的答案，因为它的问题问什么。的

Your confirmation (on whether this is correct or not) would be grateful. I know that there are other algorithms with better complexity class but since this is more efficient than O(N^2), it would be a possible answer since it's what the question asks for.

推荐答案

如果你限制了数组的5（或1000或任何其他常数为此事）的大小，那么你的算法的复杂度变 0（1），所以限制了数组的大小是一个非首发。

If you limit the size of the array to 5 (or 1000, or any other constant for that matter), then the complexity of your algorithm becomes O(1), so limiting the size of the array is a non-starter.

你能做什么，但是，是限制的值的是进入阵列。如果限制他们，说，10000，或其他一些小的数目这样，你可以做一个 O（N）算法是这样的：

What you can do, however, is limit the values that go into the array. If you limit them to, say, 10000, or some other small number like that, you could make an O(N) algorithm like this:

请布尔称为数组见过。阵列需要有最大值进入数据数组的大小。将见过数组中的所有元素假。现在通过你的数组数据，检查布尔为相应的值设置，如果是，声明副本。否则，将见过标志真。该算法在最坏情况下的 0的复杂性（N）。

Make an array of booleans called seen. The array needs to have the size of the max value that goes into your data array. Set all elements of the seen array to false. Now go through your array data, check if the boolean for the corresponding value is set, and if it is, declare a duplicate. Otherwise, set the seen flag to true. This algorithm has the complexity of O(N) in the worst case.

您可以扩大该算法允许的值中的任何范围，只要该值具有良好的哈希函数。更换阵列见过用哈希集合，并使用相同的算法。因为在一组散列添加和检索数据的时间复杂度是恒定的，该算法的渐进复杂不会改变。

You could expand this algorithm to allow any range of values, as long as the value has a good hash function. Replace the array seen with a hash set, and use the same algorithm. Since the time complexity of adding and retrieving data in a hash set is constant, the asymptotic complexity of the algorithm would not change.

最后，你可以对数组进行排序，并查找重复的 O（N * logN）的。该算法具有略差的时间复杂度，但是它的空间​​复杂度为 O（1）（使用哈希集合算法具有空间 0的复杂性（N ），这可能是显著）。

Finally, you can sort the array, and look for duplicates in O(N*logN). This algorithm has a slightly worse time complexity, but its space complexity is O(1) (the algorithms using hash set has space complexity of O(N), which may be significant).