数组中重复的数字

Wu Jun 2020-01-14 21:30:12
01 数据结构与算法 > 算法题 > 数组

题目出处

数组中重复的数字

1 题目描述

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

例如,如果输入长度为 7 的数组 {2,3,1,0,2,5,3},那么对应的输出是重复的数字 2 或者 3。

2 解题思路

思路一:排序

先排序,然后扫描相邻数字是否相同。但是排序时间复杂度为 O(nlogn)

思路二:辅助空间

扫描数组,用哈希表记录重复数字,时间复杂度 O(n),空间复杂度 O(n)

思路三:原位替换

因为数组中的数字都在 [0, n-1] 范围内,可以将值为 i 的元素调整到第 i 个位置上。在调整过程中,如果第 i 位置上已经有一个值为 i 的元素,就可以知道 i 值重复。

时间复杂度 O(N),空间复杂度 O(1)。

public class Solution {
    /**
     * Parameters:
     *    numbers:     an array of integers
     *    length:      the length of array numbers
     *    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
     *                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
     *    这里要特别注意~ 返回任意重复的一个,赋值 duplication[0]
     * Return value:       true if the input is valid, and there are some duplications in the array number
     *                     otherwise false
     */
    public boolean duplicate(int numbers[],int length,int [] duplication) {
    
        if(null == numbers || length <= 0){
            return false;
        }
        for(int i = 0; i < length; i++){
            while(numbers[i] != i){
                int value = numbers[i];
                if(numbers[i] == numbers[value]){
                    duplication[0] = value;
                    return true;
                }
                swap(numbers, i, value);
            }
        }
        return false;
    }
    private void swap(int numbers[], int i, int j){
        numbers[i] = numbers[i] + numbers[j];
        numbers[j] = numbers[i] - numbers[j];
        numbers[i] = numbers[i] - numbers[j];
    }
}

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

1 题目描述

在一个长度为 n+1 的数组里的所有数字都在 1~n 的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但是不能修改输入的数组。

例如,如果输入长度为 8 的数组 {2,3,5,4,3,2,6,7},那么对应的输出是重复的数字 2 或者 3。

2 解题思路

思路一:辅助空间

由于不能修改输入的数组,我们可以创建一个长度为 n+1 的辅助数组,然后逐一把原数组的每个数字复制到辅助数组。

如果原数组中被复制的数字是 m,则把它复制到辅助数组中下标为 m 的位置。如果下标为 m 的位置上已经有数字了,则说明该数字重复了。

由于使用了辅助空间,故该方案的空间复杂度是 O(n)。

思路二:时间换空间

避免使用辅助空间。如果数组中有重复的数,那么 n+1 个 0~n 范围内的数中,一定有几个数的个数大于 1。

按照二分查找的思路,将 1~n 的数字从中间的数字 m 分为两部分,前面一半为 1~m,后面一半为 (m+1)~n。

如果 1~m 的数字的数目大于 m,那么这一半的区间一定包含重复的数字;否则,另一半 (m+1)~n 的区间里一定包含重复的数字。

我们可以继续把包含重复数字的区间继续二分,直到找到一个重复的数字。

这种算法不能保证找到所有重复的数字。

如果输入长度为n的数组,那么函数 countRange 最多将被调用 O(logn) 次,每次需要 O(n) 的时间,因此总的时间复杂度是 O(nlogn)。但是如果区间无重复的数,则时间复杂度将变为 O(n2)。

public class Solution {

   public int getDuplication(int[] arr, int length){
       if(null == arr || length <= 0){
           return -1;
       }
       int start = 0;
       int end = length - 1;
       while(end >= start){
           int middle = ((end - start) >> 1) + start;
           int count = countRange(arr, length, start, middle);
           if(end == start){
               if(count > 1){
                   return start;
               }else{
                   break;
               }
           }

           if(count > (middle - start + 1)){
               end = middle;
           }else{
               start = middle + 1;
           }
       }
       return -1;
   }

   private int countRange(int[] arr, int length, int start, int end){
       if(null == arr){
           return 0;
       }
       int count = 0;
       for(int i = 0; i < length; i++){
           if(arr[i] >= start && arr[i] <= end){
               ++count;
           }
       }
       return count;
   }
}