剑指Offer面试题3题目二：不修改数组找出重复的数字

一、题目

在一个长度为 n+1 的数组里的所有数字都在 1~n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 8 的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字 2 或 3。

输入参数：一个整数数组numbers，数组长度length

输出参数：-1（代表输入参数出错），或者是重复的数字

二、解法

2.1分析1：辅助数组法

由于不能修改输入的数组，我们可以创建一个长度为 n+1的辅助数组，然后逐一将原数组的每个数字复制到辅助数组。如果原数组中被复制的数字是m，则把它复制到辅助数组下标为m的位置。如果下标为m的位置已经有数字了，则说明该数字重复。

该解法的空间复杂度是O（n）。

代码如下：

public int getDuplicate(int[] numbers){
  if(numbers == null || numbers.length <= 0){
    	return -1;
  }
  int[] s = new int[numbers.length];
  for(int i = 0;i < numbers.length;i++){
    s[numbers[i]] == 0 ? numbers[i]: -1;
    if(s[numbers[i]] == -1){
      return s[numbers[i]];
    }
  }
  return -1;
}

2.2分析2：二分查找的思路

在分析1的方法上进行改进，不需要额外的辅助空间。

假如没有重复数字，那么在从1~n的范围内只有n个数字，由于数字里包含超过n个数字，所以一定包含了重复的数字。

我们把1~n的数字从中间的数字m分为两部分，前面一半为1~m，后面一半为m+1~n。如果1~m的数字数目超过m，那么这一半的区域里面一定包含重复数字；否则另一半m+1~n的区间中一定包含重复的数字。我们可以继续把区间一分为二，直到找到一个重复的数字。这个过程和二分法很类似，只是多了一步统计区间中数字的数目。

public int getDuplicate(int[] numbers){
  if(numbers == null || numbers.length <= 0){
    	return -1;
  }
  int length = numbers.length
  int start = 1;
  int end = length -1;
  while(end >= start){
    int middle = ((end - start) >> 1) + start;
    int count = countRange(numbers,start,end);
    if(end == start){
      if(count > 1){
        return start;
      }else{
        break;
      }
    }
    if count >(middle - start +1)
      end = middle;
    else
      start = middle + 1;
  }
  return -1;
}

public int countRange(int[] numbers,int start,int end){
  if(numbers.length == 0){
    return 0;
  }
  int count = 0;
  for(int i = 0; i< numbers.length;i++){
    if(numbers[i]  >= start && numbers[i] <= end)
      count++;
    }
  return count;
}