剑指Offer第3题——数组中的重复数字

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

利用题干信息，所有的数字都是位于 $0$ ~ $n-1$ 范围内的。从这句话中可以获取到：如果将数组排好序，如果没有重复数字，则必定是array[i]==i，如果有重复的数字，数组中必定是缺少 $0$ ~ $n-1$ 中某些元素。

推荐的做法：当array[i] != i 时，交换array[i]和array[array[i]]，交换前判断array[i]与array[array[i]]是否相等，如果不相等，则交换，如果相等，说明找到了重复的数字。一直交换到array[i]==i为止。

public int findDuplicate(int[] array){
        if(array==null||array.length==0){
            return -1;
        }
        for (int i = 0; i < array.length; i++) {
            while(array[i]!=i){
                if(array[i]==array[array[i]]){
                    return array[i];
                }else{
                    int a = array[array[i]];
                    array[array[i]] = array[i];
                    array[i] = a;
                }
            }
        }
        return -1;
    }

其他做法：找重复数字，涉及到重复这种概念可以联想到set. 利用set唯一性可以实现。

    public int findDuplicate2(int[] array){
        if(array==null||array.length<=0){
            return -1;
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if(!set.add(array[i])){
                return array[i];
            }
        }
        return -1;
    }

其他做法2：可以额外申请一块相同大小数组的内存空间，将新申请的数组当成哈希表来使用，扫描一遍原数组，用新申请的数组存放原数组每个数字出现的次数，扫描完原数组之后扫描新数组，遇到大于1的即为重复数字

int[] hash = new int[length];
for( int i=0; i<length; i++ ){ 
  hash[array[i]]++; 
} 
for(int i=0; i<length; i++){ 
  if ( hash[i]>1 ) 
  { 
    return i;
  } 
} 
return -1;

利用set这种做法和利用hash的做法的时间复杂度与第一种相等，但要申请新的空间，空间复杂度不如第一种。

如果面试官要求不能修改输入的数组。还要空间复杂度为O(1)。可以使用时间换取空间。
查找每个数字在数组中出现的次数。 $O(n^2)$
优化可以使用二分查找的思想。
因为长度为n的数组中所有数字都是在1~n-1的范围内，可以以 $（1+n-1）/2$ 为界，分别统计 1~ $（1+n-1）/2$ 与 $（1+n-1）/2$ ~ $n-1$ 每个数字出现的次数。时间复杂度 $O(nlogn)$

最后编辑于：2019.05.09 16:37:42