题目一 找出数组中的重复的数字。 在一个长度为n的数组里所有的数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次，请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
方法1：先把输入的数组排序，然后进行遍历。但是排序一个长度为n的数组需要O（nlogn）的时间方法2：使用Hash表。从头到尾扫描这个数组，如果出现过，就打印出来，否则就加入到哈希表中。时间复杂度是O(n)，以一个大小为O(n)的哈希表为代价的。方法3：如何让时间复杂度为O（n），但是空间复杂度为O（1）。 由于数组的数字都是在0~n-1的范围内，所以就让m的数组处在m的下标下 public class Solution_tmp{ public List<Integer> duplicatenum(int[] nums){ if(nums.length <= 1 || nums == null) return new ArrayList<>(); List<Integer> res = new ArrayList<>(); int i = 0; while(i < nums.length){ if(nums[i] == i){ i++; continue; } if(nums[i] == nums[nums[i]]){ res.add(nums[i]); i++; continue; } swap(nums,i,nums[i]); } return res; } public void swap(int[] nums,int i,int j){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } public static void main(String[] args) { Solution_tmp ss = new Solution_tmp(); int[] nums = {2,3,1,0,2,5,3}; List<Integer> k = ss.duplicatenum(nums); System.out.println(k.toString()); } }题目二 不修改数组找出重复的数字 在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或3。
可以用一个辅助的数组，但是空间复杂度为O（n）在1~n的范围内，找到一个中间数m，在1至m之间统计出现的次数如果超过m，则包括重复的数字。否则m+1至n之间一定出现重复的数字。然后将目标对准某个区间，一分为二直到找到重复数字。 例如，长度为8的数组，范围是1~7,那么1到4出现了5次，5到7出现了3次，那么在1到4之间必定出现了重复的数字。再把1到4分成1到2和3到4,1到2出现了2次，3到4出现了3次，那么再把3到4分成3和4,3出现了2次，那么重复数字3 注意：这种方法并不能找出所有的重复数字。如果面试官提出不同的功能要求（找出所有的重复数字，找出所有的重复数字）或性能要求（时间复杂度、空间复杂度），那我们最终选择的算法也不一样。 package base_learn; import java.util.List; import java.util.ArrayList; public class Solution_tmp{ public int duplicatenum(int[] nums){ if(nums.length <= 1 || nums == null) return -1; int start = 1; int end = nums.length - 1; while(start <= end) { int mid = start + ((end - start) >> 1);//位移运算符优先级低于加减，一定要加小括号 int c = count(nums,start,mid); if(start == end) { if(c > 1) return start; else break; } if( c > mid - start + 1) { end = mid; }else { start = mid + 1; } } return -1; } public int count(int[] nums,int i,int j) { int c = 0; for(int k = 0;k < nums.length;k++) { if(nums[k] >= i&&nums[k] <= j) { c++; } } return c; } public static void main(String[] args) { Solution_tmp ss = new Solution_tmp(); int[] nums = {2,3,5,4,1,2,6,7}; int k = ss.duplicatenum(nums); System.out.println(k); } }位移运算符的优先级低于加减，一定要加上小括号
