面试题3：数组中的重复数字

题目1：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复的次数。请找出数组中任意一个重复的数字。例如如果输入长度为7的数组｛2，3，1，0，2，5，3｝，那么对应的输出是重复的数字2或者3。

• 方法一：因为所有数字都在0-n-1，将数组排序后遍历一遍就能知道是哪个数字重复了。数组排序时间复杂度为O(nlogn)。

• 方法二：将该数组遍历一遍存入哈希表中，在遍历元素时判断，如果哈希表中已经存在该元素，则该元素重复，如果不存在该元素，将该元素添加到集合中去。因为哈希表的判断是O(1)的，因此时间复杂度为O(n)（遍历数组），但是提升时间的代价是一个O(n)的哈希表。

• 方法三：因为范围在0到n-1的范围内，因此如果将每个位置上放置对应的脚标上的话，如果该脚标上的元素和要放入的元素相同，则有重复数字。因为每个元素至多交换两次就能到达应有的位置上，因此时间复杂度为O(n)，空间复杂度为O(1)（因为不需要额外的空间）。

  方法三的实现：(与书上大致一样，但是缺少对输入内容的判断，答案采取的是for循环，里面交换用的是while循环)

  package com.ldl.forbuilding.controller;
  
  public class HugerSingletonTest {
      public static void main(String[] args) {
          int[] arr = {2,3,1,0,2,5,3};
          System.out.println(findnumber(arr));;
      }
      public static int findnumber(int[] arr){
          int i = 0;
          while (i<arr.length){
              if (arr[i]!=i){
                  if(arr[arr[i]]==arr[i]){
                      return arr[i];
                  }
                  int temp = arr[arr[i]];
                  arr[arr[i]] = arr[i];
                  arr[i] = temp;
              }else {
                  i++;
              }
          }
          return 0;
      }
  }
  

  答案：

  public class Solution {
      public static boolean duplicate(int[] arr) {
          // 入参检查
          if (arr == null || arr.length == 0) {
              return false;
          }
          for (int i = 0; i < arr.length; i++) {
              if (arr[i] < 0 || arr[i] >= arr.length) {
                  return false;
              }
          }
  
          // 遍历数组
          for (int i = 0; i < arr.length; i++) {
              while (arr[i] != i) {
                  if (arr[i] == arr[arr[i]]) {
                      System.out.println(arr[i]);
                      return true;
                  }
                  // 替换
                  int temp = arr[i];
                  arr[i] = arr[temp];
                  arr[temp] = temp;
              }
          }
          return false;
      }
  
      public static void main(String[] args) {
          int[] arr = {1, 1, 2, 4, 2, 5, 6};
          boolean result = duplicate(arr);
          System.out.println(result);
      }
  }
  

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

• 方法一：新建一个n+1大小的数组，遍历输入数组，如果该元素大小对应在新建数组脚标位置上为空元素，则将该元素放入新数组中，以此类推，当遍历到的元素对应的新建数组脚标上的元素不为空，说明出现重复元素。时间O(n)，空间O(n)。

  • 手写

    package com.ldl.forbuilding.controller;
    
    public class HugerSingletonTest {
        public static void main(String[] args) {
            int[] arr ={2,3,5,4,3,2,6,7};
            System.out.println(findnumber(arr));;
        }
        public static boolean findnumber(int[] arr){
            int[] temp = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                if(arr[i]==temp[arr[i]]){
                    System.out.println(arr[i]);
                    return true;
                }else {
                    temp[arr[i]]=arr[i];
                }
            }
            return false;
        }
    }
    

  • 答案

    public class Solution {
        public static int getDuplication(int[] arr) {
            // 入参检查
            if (arr == null || arr.length == 0) {
                return -1;
            }
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] < 1 || arr[i] >= arr.length) {
                    return -1;
                }
            }
    
            int[] tempArr = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == tempArr[arr[i]]) {
                    return arr[i];
                }
                tempArr[arr[i]] = arr[i];
            }
            return -1;
        }
        public static void main(String[] args) {
            int[] numbers = {2, 1, 5, 4, 3, 2, 6, 7};
            System.out.println(getDuplication(numbers));
        }
    }
    

  假如面试官要求空间复杂度为O(1)时，我们要用到方法二。

• 方法二：通过二分查找(折半查找)的方式，判断1_{m中的元素出现的次数，如果小于m次，则重复元素在m+1}n中。将m+1~n再进行对半拆分，判断元素出现次数。 举例说明：长度为8的数组，元素范围为1_7。那么14出现次数为5次(通过直接遍历数组，判断每个元素是不是大于等于1且小于等于4)，大于4，因此1_{4中一定有重复元素。再拆分，1}2出现次数为2次(注意，这个时候2也是重复元素，但是该方法判断不出来！)，3_{4出现了3次。因此3}4中一定有重复元素。再拆分，3出现了2次，4出现了一次，找到重复元素3。

  • 手写（看答案写出来的。。。二分查找忘干净了）

    package com.ldl.forbuilding.controller;
    
    public class HugerSingletonTest {
        public static void main(String[] args) {
            int[] arr ={2,3,5,4,3,2,6,7};
            System.out.println(findnumber(arr));;
        }
        public static int findnumber(int[] arr){
            // 入参检查
            if (arr == null || arr.length == 0) {
                return -1;
            }
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] < 1 || arr[i] >= arr.length) {
                    return -1;
                }
            }
            int left = 1;
            int right = arr.length-1;
            while (left<=right){
                int mid = (right-left)/2+left;
                int count = findcount(arr,left,mid);
                if(left==right){
                    if(count>1){
                        return left;
                    }else {
                        break;
                    }
                }
                if(count>mid-left+1){
                    right=mid;
                }else {
                    left=mid+1;
                }
            }
            return -1;
        }
        public static int findcount(int[] arr,int left,int right){
            int count =0 ;
            for (int i = 0; i <arr.length ; i++) {
                if(arr[i]>=left&&arr[i]<=right){
                    ++count;
                }
            }
            return count;
        }
    }
    

    二分查找O(logn)，遍历长度为n的数组O(n)，因此输入长度为n的数组，那么findcount函数将被调用O(logn)次，每次时间为O(n)，因此总时间复杂度为O(nlogn)，空间复杂度为O(1)。与之前的时间和空间都为O(n)相比是时间换空间。