当前位置 : 主页 > 编程语言 > java >

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

来源:互联网 收集:自由互联 发布时间:2023-09-14
一、题目 在一个长度为 n+1 的数组里的所有数字都在 1~n 的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入

一、题目

在一个长度为 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;
}
上一篇:[转自网络]Mysql中的Explain解析
下一篇:没有了
网友评论