您给出个整数的排序的数组，你想了解是否有阵列中的任何重复（即任意整数不止一次出现更多）。 描述一个算法（有两个嵌套的循环来实现），以做到这一点。的

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). Describe an algorithm (implemented with two nested loops) to do this.

这是我停留在这样的问题： 你怎么能限制输入数据，以达到更好的大O的复杂性？描述一个算法来处理这​​有限的数据，以寻找是否有任何重复。什么是大O的复杂性？的

The question that I am stuck at is: How can you limit the input data to achieve a better Big O complexity? Describe an algorithm for handling this limited data to find if there are any duplicates. What is the Big O complexity?

您的帮助将大大AP preciated。这是不相关的我的课程，转让或课程和这样的。这是从previous一年的试卷，我做了一些自学，但似乎被卡在这个问题上。我能想出的唯一可能的解决方案是：

Your help will be greatly appreciated. This is not related to my coursework, assignment or coursework and such. It's from the previous year exam paper and I am doing some self-study but seem to be stuck on this question. The only possible solution that i could come up with is:

如果我们限制数据，并使用嵌套循环来执行操作，以发现是否有重复。的复杂性将是 O（n）的仅仅是因为时间的操作用来执行量成比例的数据量。

If we limit the data, and use nested loops to perform operations to find if there are duplicates. The complexity would be O(n) simply because the amount of time the operations take to perform is proportional to the data size.

如果我的回答是没有意义的，那么请忽略它，如果你可以的话，请提出可能的解决方案/工作了这个答案。谢谢。 如果有人可以帮助我解决这个问题的回答，我将不胜感激，因为我已经尝试了无数可能的解决方案，所有这一切似乎是不正确的。感谢您的时间。

If my answer makes no sense, then please ignore it and if you could, then please suggest possible solutions/ working out to this answer. Thanks. If someone could help me solve this answer, i would be grateful as i have attempted countless possible solution, all of which seems to be not the correct one. Thank you for your time.

Editied部分，再次..另一种可能的解决方案（如果有效！）：的  我们可以实现一个循环数组排序，以便它排序数组（从最低整数最高的整数），因此，重复的将是紧挨着对方使他们更容易和更快地被识别。 大O的复杂性仍然是为O（n ^ 2）。 由于这是直线型，这将简单地使用第一环路和迭代正1次，因为我们所得到的数组中的索引（在第一次迭代它可能是，例如，1）和其存储在一个变量名'当前的。  循环将+1每次通过迭代更新当前的变量，即循环中，我们现在写另一个循环的当前数目比作下一个号码，如果它等于下一个数字，我们可以打印使用printf语句否则我们回迁外环更新由+ 1（在阵列中的下一个值）当前的变量，并更新当前的值之后保持数的值的下一个变量。

Editied part, again.. Another possible solution (if effective!): We could implement a loop to sort the array so that it sorts the array (from lowest integer to highest integer), therefore the duplicates will be right next to each other making them easier and faster to be identified. The big O complexity would still be O(n^2). Since this is linear type, it would simply use the first loop and iterate n-1 times as we are getting the index in the array (in the first iteration it could be, for instance, 1) and store this in a variable names 'current'. The loop will update the current variable by +1 each time through the iteration, within that loop, we now write another loop to compare the current number to the next number and if it equals to the next number, we can print using a printf statement else we move back to the outer loop to update the current variable by + 1 (next value in the array) and update the next variable to hold the value of the number after the value in current.

推荐答案

您可以做线性（ O（N）），因为如果你使用的哈希表的任何输入（其中具有恒定的查找时间）。

You can do linearly (O(n)) for any input if you use hash tables (which have constant look-up time).

不过，这是不是你正在询问。

However, this is not what you are being asked about.

通过限制可能的值的数组中，就可以实现线性的性能。

By limiting the possible values in the array, you can achieve linear performance.

例如，如果你的整数有一系列 1..L ，您可以分配长度的位数组→ ，初始化为0，并遍历您的输入数组，检查和翻转的相应位为每个输入。

E.g., if your integers have range 1..L, you can allocate a bit array of length L, initialize it to 0, and iterate over your input array, checking and flipping the appropriate bit for each input.