数组中重复的数字weixin43831728的博客-

数组中重复的数字

题目描述：

• 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

解题思路：

思路一：

• 解决这个问题的一个简单的方法就是先对输入的数组进行排序，从排好序的数组中找出第一个重复的数字是很容易做到的，只需要从头到尾遍历数组就可以的，可以利用sort对数组进行排序，排序一个长度为n的数组的时间复杂度为nlogn.

class Solution { public: // Parameters: //        numbers:     an array of integers //        length:      the length of array numbers //        duplication: (Output) the duplicated number in the array number // Return value:       true if the input is valid, and there are some duplications in the array number //                     otherwise false bool duplicate(int numbers[], int length, int* duplication) { //采用排序的方法 if(NULL==numbers||length==0) return false; sort(numbers,numbers+length-1); for(int i=0;i<length;i++) { if(numbers[i]==numbers[i+1]) {                 duplication[0]=numbers[i]; return true; } } return false; } }; 

思路二：

• 还可以利用哈希表来解决这个问题，从头到尾扫描整个数组的每个数字，每次扫描到一个数字的时候，都可以用O(1)的时间来判断哈希表中是否已经有了这个元素，如果说哈希表中还没有这个元素，就把他加入到哈希表中，如果说，哈希表中已经存在了这个元素的话，那么就找到了一个重复的数字，这个算法的时间复杂度为O(N),但是它时间复杂度的提升是建立在一个空间为O(N)的哈希表为代价的，就相当于是在用空间换时间

class Solution { public: // Parameters: //        numbers:     an array of integers //        length:      the length of array numbers //        duplication: (Output) the duplicated number in the array number // Return value:       true if the input is valid, and there are some duplications in the array number //                     otherwise false bool duplicate(int numbers[], int length, int* duplication) { //先判断数组的合法性 if(NULL==numbers||length==0) return false; int hashtable[255]={0}; //定义哈希表 for(int i=0;i<length;i++) {             hashtable[numbers[i]]++; } for(int i=0;i<length;i++) { if(hashtable[numbers[i]]>1) {                 duplication[0]=numbers[i]; return true; } } return false; } }; 

思路三：

• 我们注意到数组中的数字都在0~n-1的范围内。如果说这个数组中没有重复的数字，那么数组在排序之后的数字i就会出现在下标为i的位置上，由于数组中是有重复的数字的，所以说有些位置可能存在有多个数字，同时有些位置可能是没有数字的
• 那么现在，我们就重新对这个数组进行排序的操作，从头到尾扫描这个数组中的每一个元素，当扫描到下标为i的数字的时候，首先比较这个数字(用m表示)是不是等于i。如果是的话，那么就接着去扫描下一个数字，如果不是的话，就拿他和第m个数字进行交换。如果他和第m个数字相等的话，就找到了了重复的数字(因为这个数字在下标为i和m的位置都出现了)；如果他和第m个数字不相等的话，那么就把第i个数字和第m个数字进行交换，把m放到属于他的位置，接下来再重复的去进行这个比较，交换的过程，直到我们发现了重复的数字

class Solution { public: // Parameters: //        numbers:     an array of integers //        length:      the length of array numbers //        duplication: (Output) the duplicated number in the array number // Return value:       true if the input is valid, and there are some duplications in the array number //                     otherwise false bool duplicate(int numbers[], int length, int* duplication) { if(NULL==numbers||length==0) return false; for(int i=0;i<length;i++) { if(numbers[i]<0||numbers[i]>length) { return false; } } for(int i=0;i<length;i++) { while(numbers[i]!=i) { if(numbers[i]==numbers[numbers[i]]) {                     duplication[0]=numbers[i]; return true; } int temp=numbers[i];                 numbers[i]=numbers[temp];                 numbers[temp]=temp; } } return false; } }; //虽然说代码中有两层循环，但是每个数字最多交换两次就能找到属于它自己的位置了，所以说时间复杂度是O(n),空间复杂度是O(1) 

在上述的代码总，找到的重复数字通过参数duplication传给函数的调用者，而函数的返回值表示数组中是否有重复的数字，当输入的数组中有重复的数字的话，就会返回true，如果没有重复数字的话，就会返回false

测试用例

• 长度为n的数组中包含一个或者多个重复的数字
• 数组中没有重复的数字
• 无效的测试用例