剑指 面试题3：数组中重复的数字 题目一：找出数组中重复的数字。 在一个长度为 n 的数组里所有数字都在0–（n-1）的范围内。数组中某些数字是重复的，但不知道有几个数字重复了， 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如：如果输入长度为7的数组{2,3,1,0,2,5,3} 那么对于的输出是重复的数字2，或者3。 解题思路： 1. 对输入的数组进行排序，再扫描排序后的数组就能很容易找出重复的数字，排序需要的时间复杂度为O(n*logn) 2. 利用哈希表解决，用一个长度为n辅助数组，其数组下标为key，下标所指元素为value；生成map表以后， 再扫描map也能很快找到重复数字。该算法：时间复杂度为O(n)，因为用了一个长度为n的辅助数组，所以空间复杂度为O(n) 3. 本题有一个很关键的话“在一个长度为 n 的数组里所有数字都在0–（n-1）的范围内”，这句话隐含一个条件就是：如果这个数组 是升序排好且无重复的，那么数组的元素和数组的下标是一一对应的（即相同），所以就可以根据比较数组元素与下标是否相等来 判断数组中是否有重复数字。由于本题数组的这个特性，我们也并不需要先对它排序再判断是否有重复数字；而是一边排序一边对其 判断是否有重复数字。 具体操作如下：if(i==a[i]){a[i]已经排好序，i++ 看下一个元素是否排好} while（i!=a[i]){ 先比较a[i]是否等于第a[i]个数字，若等于则a[i]重复了，打印该数字即可； 若不相等，则需要对a[i]进行排序，即需要将a[i]和下标为a[i]的元素进行交换。} 该算法不需要辅助数组，所以其空间复杂度为O(1)；时间复杂度为O(n)
import java.util.Arrays; import java.util.Scanner; public class demo04 { public static void main(String[] args){ Scanner input = new Scanner(System.in); int[] arr = {2,3,1,0,2,5,3}; System.out.println("第一种方法：" + way01(arr)); System.out.println("第二种方法：" + way02(arr)); System.out.print("第三种方法：" + way03(arr)); } // 方法一： public static int way01(int[] arr){ int reNum = -1; int[] hashMap = new int[arr.length]; if (arr==null || arr.length < 1){ return reNum; } Arrays.sort(arr); for (int i = 0; i < arr.length; i++) { if (i < arr.length-1 && arr[i] == arr[i+1]){ reNum = arr[i]; } /* 本题的另一种判断重复数字的方法 if (arr[i] != i){ reNum = arr[i]; break; } */ } return reNum; } // 方法二： public static int way02(int[] arr){ int reNum = -1; int[] hashMap = new int[arr.length]; if (arr==null || arr.length < 1){ return reNum; } for (int i = 0; i < arr.length; i++) { hashMap[arr[i]]++; } for (int i = 0; i < hashMap.length; i++) { if (hashMap[i] > 1){ reNum = i; break; } } return reNum; } // 方法三： public static int way03(int[] arr){ int reNum = -1; if(arr==null || arr.length < 1){ return reNum; } for (int i = 0; i < arr.length; i++) { while (i != arr[i]){ if(arr[i]==arr[arr[i]]){ reNum = arr[i]; break; }else { exchange(arr,i,arr[i]); } } } return reNum; } public static void exchange(int[] a,int i,int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp; } }