Java教程

剑指offer第二版面试题3:数组中的重复数字(java)

本文主要是介绍剑指offer第二版面试题3:数组中的重复数字(java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

面试题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)时,我们要用到方法二。

  • 方法二:通过二分查找(折半查找)的方式,判断1m中的元素出现的次数,如果小于m次,则重复元素在m+1n中。将m+1~n再进行对半拆分,判断元素出现次数。 举例说明:长度为8的数组,元素范围为17。那么14出现次数为5次(通过直接遍历数组,判断每个元素是不是大于等于1且小于等于4),大于4,因此14中一定有重复元素。再拆分,12出现次数为2次(注意,这个时候2也是重复元素,但是该方法判断不出来!),34出现了3次。因此34中一定有重复元素。再拆分,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)相比是时间换空间。

这篇关于剑指offer第二版面试题3:数组中的重复数字(java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!