要求：在一个长度为n+1的数组，数组内值为1~n，不能修改原本数组 思路：使用分治思维，在一个长度为n+1的数组，数组内值为1~n的情况下，必定存在数据重复情况。我们不在数组上做文章，将焦点聚集在1-n的数值上。 将数值1-n分为两部分[1，(n+1)/2]，[(n+1)/2+1，n]，统计两部分数值在数组中出现的次数，若大于数值的个数，则必定重复，后续重复即可。 例如： 数组[1,2,3,4,5,3]，数值为1-5，我们将数值分为[1，2，3]和[4，5]，统计[1，2，3]在数组中出现的次数。若大于3次则必定存在重复。
public class Offer06 { public static void main(String[] args) { int[] arr = new int[]{1,2,3,4,5,3}; int start = 1; int end = arr.length; //分治 while (start<end){ int middle = (start + end)/2; int count = 0; //计数 for (int i=0;i<arr.length;i++){ if(arr[i]>=start&&arr[i]<=middle)count++; } //判断计数情况 if(count>middle-start+1){ end = middle; }else{ start = middle+1; } } System.out.println(end); }