题目二：数组中重复数字

题目描述

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

思路

思路一：暴力算法

遍历所有数据。

/**** @param numbers* @param length* @param duplication* @return* 29ms 9588k  时间复杂度O(n^2)*  // Parameters://    numbers:     an array of integers//    length:      the length of array numbers//    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;//                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++//    这里要特别注意~返回任意重复的一个，赋值duplication[0]// Return value:       true if the input is valid, and there are some duplications in the array number//                     otherwise false*/public static  boolean duplicate1(int numbers[],int length,int [] duplication) {for(int i=0;i<length;i++){for(int j=i+1;j<length;j++){if(numbers[i]==numbers[j]){duplication[0]=numbers[i];return true;}}}return false;}

思路二：先排序，再比较相邻的数据

    /**** @param numbers* @param length* @param duplication* @return* 思路二：将数组排序：排完序 比较相邻的数据时间复杂度为 O(NLOGN)*/public static  boolean duplicate2(int numbers[],int length,int [] duplication) {Arrays.sort(numbers);for(int i=0;i<length-1;i++){if(numbers[i]==numbers[i+1]){duplication[0]=numbers[i];return true;}}return false;}

思路三：使用HashSet

思路三：利用HashSet解决问题
遍历数组，如果在HashSet中存在该元素，则结束
如果不存在则将该元素加入HashSet

时间复杂度：O(n)

空间复杂度:O(n)

    public static  boolean duplicate3(int numbers[],int length,int [] duplication){//定义HashSetHashSet<Integer> hashSet = new HashSet<>();for(int i=0;i<length;i++){if(hashSet.contains(numbers[i])){//在HashSet中存在该元素duplication[0]=numbers[i];return true;}else{  //在HashSet中不存在该元素hashSet.add(numbers[i]);}}return false;}

思路四：按位置比较交换排序

我们注意到数组中的数字都在0~n-1中，
如果这个数组中没有重复的数字，那么当数组排序之后数字i将出现在位置i的位置上
由于数组中有重复的数字，有些位置可能存在多个数字，同时可能有些位置没有数字。

思路四： 从头到尾依次扫描这个数组。
当扫描到下标为i数组时，首先比较这个数字（用m表示）是不是等于i。
如果是，接着扫描下一个数字，
如果不是，则拿他和第m个数字进行比较。如果它和第m个数字相等，就找到了一个重复数字（该数字在下标i和m都出现了) 如果它和第m个数字不相等，就把第i个数字和第m个数字交换，把m放到他的位置。
接下来重复这个比较交换的过程

核心：n个长度的数组的n个数据若无重复，则必然可以按照顺序依次排放，

​ 其实就是一种选择排序；但是这种算法会破坏数组的结构

时间复杂度：O(n)

 public static  boolean duplicate4(int numbers[],int length,int [] duplication){for(int i =0;i<length;i++){//从头到尾扫描整个数组int value = numbers[i];while(value!=i){//当前这个数字不等于i//和第value个数字比较，如果相等就找到了一个重复数值if(numbers[value]==value){duplication[0]=value;return true;}else{//不相等，则把第i个数字和第value个数字交换int temp = numbers[i];numbers[i]=numbers[value];numbers[value]=temp;}}}return  false;}

思路五：基于数据个数的二分查找

思路5： 为什么数组中有重复数据？

​ 假设没有重复数字，那么从1~n的数据范围内只有n个数字。

​ 由于现在数组里包含超过n个数字，所以一定包含了重复数字。

​ 看起来某个范围内数字的个数对解决这个问题很重要

​ 我们把从1_{n的数字从中间数字m分为两部分，前面一部分为1}m,后面一部分为m+1~n

​ 如果1~m的数字的数目超过m那么这一半一定包含了重复数字；否则另外一半包含了重复数字 *

​ 我们可以继续吧包含重复数字的区间一分为二，直到找到一个重复的数字。

​ 这个过程个二分查找算法狠类似，只是多了一步统计区间里数字的数目。

时间复杂度：O(nLogn)

    public static  boolean duplicate5(int numbers[],int length,int [] duplication) {int start = 1;//可能的最小值int end = length;//可能的最大值int mid = (start+end)/2;//计算中值 便于二分查找while(end>=start) {//计算在 start - mid中间值出现的次数int count = countRange(numbers, length, start, mid);System.out.println(start+"---"+mid+"值出现的次数--"+count);if (start == end) { //首末值相等，一个数据if (count > 1) {  //假如count值大于1,说明改数据出现了不止一次duplication[0]=start;return true;} else {  //说明没有重复break;}}if (count > mid - start+1) { //在start-mid中华间数据个数多了，则继续查找end = mid;mid = (start + end) / 2;} else {  //start = mid + 1;mid = (start + end) / 2;}}return false;}/*** 计算在数组中 start-end数据出现的次数* @param arr* @param lenght* @param start* @param end* @return*/public  static  int countRange(int[] arr,int lenght,int start,int end){int  count = 0;for(int i=0;i<lenght;i++){//遍历数组，进行统计在start于end之间数据的个数if(arr[i]>=start&&arr[i]<=end){count++;}}return count;}

这种算法不能保证找出所有重复数据