There is an array of 1001 elements which range from 1 to 1000. Only one element is repeated in the array while the others exist only once in the array. Which of the following algorithms is the fastest?

1-1000放在含有1001个元素的正整数数组中，只有唯一的一个元素值重复，其它均只出现一次。下列哪种算法查找这个重复元素最快？

A. Enumerate all the paris in the array, find the pair with same values (枚举1001个元素中所有的正整数对，找到值相同的那一对) C(n,2)

B. XOR all the numbers in the array together, then XOR number from 1 to 1000 (现将数组中所有数异或在一起，再与1-1000各异或一次) O(n)

C. Sort the array and then make sequential search(将数组进行排序，再线性搜索) O(nlogn)

D. Sort the array and then make binary search(将数组进行排序，再二分搜索) O(nlogn)

Correct Answer : C

link: https://www.geeksforgeeks.org/find-the-two-repeating-elements-in-a-given-array/
https://www.xuetangx.com/learn/THU08091000327/THU08091000327/5883587/exercise/9215891