限定条件是每个数组元素只能访问一次，并且不能使用辅助存储空间。那么，就不能使用Hash法。而如果可以使用辅助空间，最简单办法就是Hash法，而在Python中，可以使用字典来代替Hash法的功能。具体过程如下：
首先定义一个字典，将字典中的元素值都初始化为0，将原数组中的元素逐一映射到该字典的key中，当对应的key中的value值为0时，则将该key的value值为1，当对应的key的值为1时，则表明该位置的数在原数组中是重复的。
性能分析：这种方法是一种典型的以空间换时间的方法，它的时间复杂度为O(N)，空间复杂度为O(N)。在没有明确限制下，不失为一种好方法，但并不适合这道题目。
1001个数中有1000个是固定的，唯一一个不固定的数也知道其范围，那么用累加求和法就好了。将数组中的所有N+1个元素相加，然后用得到的和减去1+2+3……+N的和，得到的差即为重复的元素的值。
性能分析：时间复杂度为O(N)，空间复杂度为O(1)。
累加求和的方法，存在一个潜在的风险，就是当数组中的元素值过大或者数组过长，计算的和值有可能会出现溢出，进而无法求解出数组中的唯一重复元素。
鉴于求和法存在的局限性，可以采用位运算中异或的方法。异或：相同元素异或，结果为0；不同元素异或，结果非0；任何数和0异或，结果为该数。
性能分析：时间复杂度为O(N)，也没有申请辅助的存储空间。
数值取值操作可以看作一个特殊的函数f:D->R，定义域为下标值0-1000，值域为1到1000。如果对任意一个数i，把f(i)叫做它的后继，i叫f(i)的前驱。重复的那个数字有两个前驱。
利用下标与单元中所存储的内容之间的特殊关系，进行遍历访问单元，一旦访问过的单元赋予一个标记，利用标记作为发现重复数字的关键。
以array=[1,3,4,3,5,2]为例：
- array[0]的值为1，未被标记，接下来遍历array[1]，同时标记array[0],比如，标记为相反数-1;
- array[1]的值为3，未被标记，接下来遍历array[3]，同时标记array[1]；
- array[3]的值为3，未被标记，接下来遍历array[3]，同时标记array[3]；
- array[3]的值为-3，说明3已经被遍历过了，找到重复元素。
性能分析：时间复杂度为O(N)，也没有申请辅助的存储空间。
可以采用类似于单链表是否存在环的方法进行问题求解。“判断单链表是否存在环”是一个非常经典的问题，同时单链表可以采用数组实现。本题可以转化为“已知一个单链表中存在环，找出环的入口点”这个问题。本题可借鉴第一章 链表的第6题，方法为快慢指针法。
性能分析：时间复杂度为O(N)，也没有申请辅助的存储空间。
首先定义两个变量max和min，分别记录数组中最大值和最小值，并将其都初始化为数组的首元素的值，然后从数组的第二个元素开始遍历数组元素，如果遇到比max大的元素，则该数组元素就是当前的最大值，将其赋值给max；min同理。
性能分析：时间复杂度为O(N)。最差的情况下比较次数达到了2n-2次，最好的情况下比较次数为n-1。
分治法：将一个规模为n的、难以直接解决的大问题，分割成k个规模较小的子问题，采取分而治之的策略得到各个子问题的解，然后将各个子问题的解进行合并，从而得到原问题的解。
本题中，将数组两两一对分组，如果数组元素个数为奇数个，就单独为一组，然后，将每组中较小的放左边，较大的放右边。接着，在每组的左边部分找最小值，右边部分找最大值，就能得到最大值和最小值。
性能分析：分组需要n/2次，比较需要n/2-1和n/2-1次。总共比较的次数大约为3n/2-2次。
将数组分成左右两部分，先求出左半部分的最大值和最小值，再求出右半部分的最大值好最小值，然后综合起来。总体是一个递归过程，对于划分后的左右两部分，重复这个过程，直到划分区间内只剩一个元素或者两个元素为止。
性能分析：这种方法与分治法的思路从本质上是一样的，不过这种方法用递归来实现，比较次数也为3n/2-2次。
一个数组x[0...n-1]，现在把它分为两个子数组：x1[0...m]和x2[m+1...n-1]，交换这两个子数组，使数组x由x1x2变成x2x1。直接遍历法比较低效，而比较高效的方法是二分查找法。
经过旋转后的数组实际上可以划分为两个有序的子数组，前面的子数组的元素值都大于或者等于后面子数组的元素值。可以采用二分查找的思想不断缩小查找范围，最终找到最小元素。根据旋转定义，第一个元素应该是大于或者等于最后一个元素的(旋转个数为0时除外)。给定数组arr，定义变量start和end，表示数组的第一个元素和最后一个元素的下标。mid=(start+end)/2:
- 如果arr[mid]<arr[mid-1]，则arr[mid]一定是最小值；
- 如果arr[mid+1]<arr[mid]，则arr[mid+1]一定是最小值；
- 如果arr[end]>arr[mid]，则最小值一定在数组左半部分；
- 如果arr[mid]>arr[start]，则最小值一定在数组右半部分；
- 如果arr[start]=arr[mid]且arr[end]=arr[mid],则此时无法区分最小值在哪半部分，只能分别在左右两部分求最小值minL和minR，最后求出minL和minR的最小值。
性能分析：二分查找的时间复杂度为O($ \log _2 ^N$),只有在最坏的第五种情况下的时间复杂度为O(N)。
n-1个整数组成的数组序列，其元素都是1到n中不同的整数。如果加上这个缺失的数，数组之和为一个定值。a为n-1个数的和，b为n个数的和，缺失的数字就是b-a。
性能分析：时间复杂度为O(N)。求和的过程中，计算有溢出的可能性，在计算的时候可以考虑位运算。
定义两个数a和b，其中a是1到n的异或运算，b表示的是数组中所有数到的异或运算结果，缺失的数字的值为a^b的值。
性能分析：计算a时对数组进行了一次遍历，时间复杂度为O(N)，计算b的时候循环执行的次数也为N，所以时间复杂度为O(N)。
定义一个字典，把数组元素的值作为key，遍历整个数组，如果key值不存在，则将value设为1，如果key值已经存在，则翻转该值，在完成数组遍历后，字典中value为1的就是出现奇数次的数。
性能分析：对数组进行了一次遍历，时间复杂度为O(N)，但是申请了额外的存储，空间复杂度为O(N)。
如果从头到尾依次异或每一个元素，那么异或运算的结果自然也就是只出现奇数次的数字的异或，因为出现偶数次的数字会通过异或运算全部消掉。假设这两个出现奇数次的数分别为a和b，将二者异或运算的结果记为c，由于a和b不相等，c的值也不会是0，此时只需要知道c对应的二进制数中某一位为1的位数N。然后将c与数组中所有第N位为1的数进行异或，异或结果就是a，b中一个，然后用c异或其中一个数，就可以求出另外一个数了。 性能分析：首先对数组进行了一次遍历，时间复杂度为O(N)，寻找对应位值为1的位数，时间复杂度为O(1)，接着又遍历了一次数组，时间复杂度为O(N)，因此，整体的时间复杂度为O(N)。
对于一个有序的数组而言，能非常容易找到数组中第k小的数，因此，可以通过局部排序的方法来找出第k小的数。下面有几种不同的办法来实现局部排序。
通过对选择排序进行改造，第一次遍历从数组中找出最小的数，第二次遍历从剩下的数中找出最小的数，第k次遍历就可以从N-k+1个数中找出最小的数。时间复杂度为O(N*k)。
快速排序的基本思想为：将数组array[start...end]中某一个元素作为划分依据，然后把数组划分为三部分：1.array[start...(i-1)]，元素小于或等于array[i]；2.array[i]；3.array[(i+1)...end]，元素大于array[i]。在此基础上求出第k小的元素。
- 如果i-start == k-1，说明array[i]就是第k小的元素，直接返回array[i]；
- 如果i-start > k-1，说明第k小的元素在array[start...(i-1)]中，递归地找出第k小的元素；
- 如果i-start < k-1，说明第k小的元素在array[(i+1)...end]中，递归地找出第k小的元素。
性能分析：快速排序的平均时间复杂度为O($ N log_2^N$)，而这里不用对子数组进行排序处理，平均时间复杂度小于O($ N log_2^N$)。缺点是改变了数组中数据原来的顺序，如果申请额外的N个空间，会增加算法的空间复杂度。
对数组进行双重遍历，外层循环遍历查找num1，内存循环从头开始遍历找到num2，每当遍历到num2，就计算它们的距离dist，当遍历结束后最小的dist值就是它们的最小的距离。
性能分析：对数组进行两次遍历，时间复杂度为O(N^2)。
蛮力法中的内层循环对num2的位置进行了很多次重复的查找。可以采用动态规划的方法把每次遍历的结果都记录下来从而减少遍历次数。具体实现思路为：
- 遍历数组，当遇到num1时，记录下num1值对应的数组下标的位置index1，通过求index1与上次遍历到num2下标的位置的值index2的差求出最近一次遍历到的num1与num2的距离。
- 当遇到num2时，记录下num2值对应的数组下标的位置index2，通过求index2与上次遍历到num2下标的位置的值index1的差求出最近一次遍历到的num1与num2的距离。
性能分析：这种方法只需要对数组进行一次遍历，时间复杂度为O(N)。
三个升序整数数组中各找出一个元素。当ai<bi<ci时，它们的距离肯定为Di=ci-ai，这时候没必要求bi-ai与ci-ai的值了，接下来分为如下三种情况讨论：
- 如果接下来求ai、bi、c(i+1)的距离，由于c(i+1)>ci，它们的距离必为D(i+1)=c(i+1)-ai，D(i+1)不可能为最小距离。
- 接下来求ai、b(i+1)、ci的距离，由于b(i+1)>bi，如果b(i+1)<ci，它们的距离仍为D(i+1)=Di;如果b(i+1)>ci，D(i+1)不可能是最小距离；
- 接下来求a(i+1)、bi、ci的距离,如果a(i+1)<ci+|ci-ai|，此时它们的距离D(i+1)=max(ci-a(i+1),ci-bi)，D(i+1)<Di，所以D(i+1)有可能是最小值。
综上所述，在求最小距离的时候只需要考虑第三种情况。具体思路为：从三个数组的第一个元素开始，首先求出他们的距离minDist，接着找出这三个数中最小数所在的数组，对这个数组进行往后遍历，接着求出三个数组中当前遍历元素的距离，如果比minDist小，则把当前距离赋值给minDist，直到遍历完其中一个数组。
性能分析：最多只要对三个数组分别遍历一遍，时间复杂度为O(l+m+n)。