剑指offer No.3.2 不修改数组找出重复的数字

剑指offer60天计划

Posted by liuwenzi on July 21, 2020
阅读数:

不修改数组找出重复的数字

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

题解

  • 利用额外的数组空间,将数组复制到另一数组A中,当原数组中元素已经存在数组A时,则证明原数组元素是重复元素

    • 空间复杂度:O(n)
    • 时间复杂度:O(n)
  • 利用二分法,将数字1~n的数字从中间的数字m分为两个部分,前一半为1~m,后一半为m+1~n。如果1~m在数组中出现的次数超过m次,则1~m中有重复的数字,如小于等于m,则m+1~n中包含重复的数字。接下来,继续把包含重复数字的区间进行二分,直到找到一个重复数字

    • 空间复杂度O(1)
    • 时间复杂度O(nlogn)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    
    class Solution {
        public int findRepeatNumber(int[] nums) {
            int start = 1,end = nums.length-1;
            while(start < end){
                int middle = (start + end)/2;
                int occurrenceNumber = 0;
                for(int num:nums)
                {
                   if(num<=middle){
                    occurrenceNumber++;
                   } 
                }
                if(occurrenceNumber > middle){
                    end = middle;
                }else{
                    start = middle + 1;
                }
            }
            return start;
        }
      
          
    }