2-数组中重复的数字

时间:2022-08-28 19:53:18

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

  • 排序
  • 哈希表。从头到尾按顺序扫描数组的每个数字,每扫描到一个数字,都可以用O(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字,就把它加入哈希表,如果哈希表里已经存在该数字,就找到一个重复的数字。这个算法的时间复杂度是O(n),但它提高时间效率是以一个大小为O(n)的哈希表为代价的
  • 重排数组。数组元素都在0~n-1之间,如果这个数组没有重复的数字,那么当数组排序之后数字i会出现在下标为i的位置。从头到尾依次扫描这个数组中的每个数字,当扫描到下标为i的数字时,首先比较这个数字(m)是不是等于i;如果是,则接着扫描下一个数字;如果不是,则再拿它和第m个数字进行比较,如果它和第m个数字相等,就找到了一个重复的数字,如果它和第m个数字不相等,就把第i个数字和第m个数字交换,把m放到属于它的位置。接下来重复这个比较、交换的过程,直到发现一个重复的数字。
bool duplicate(int numbers[], int length, int* duplication){
    if(numbers == nullptr || length < 0)
        return false;
    for(int i=0; i < length; i++){
        if(numbers[i]<0 || numbers[i]>length-1)
            return false;
    }
    for(int i=0; i < length; i++){
        while(numbers[i] != i){
            if(numbers[i] == numbers[numbers[i]]){
                *duplication = numbers[i];
                return true;
            }
            int temp = numbers[i];
            numbers[i] = numbers[temp];
            numbers[temp] = temp;
        }
    }
    return false;
}

二、问题描述: 不修改数组找出重复的数字
在一个长度为n+1的数组里的所有数字都在1-n的范围内,所以数组中至少有一个数字是重复的。请找出数组里任意一个重复的数字,但不能修改数组

  • 创建一个长度为n+1的辅助数组,然后逐一把原数组的每一个数字复制到辅助数组。如果原数组中被复制的数字是m,则把它复制到辅助数组中下标为m的位置,这样就很容易发现哪个数字是重复的。该方案需要O(n)的辅助空间
  • 某范围里数字的个数。把1-n的数字从中间的数字m分为两部分,前面一半为1-m,后面一半为m+1-n。如果1-m的数字的个数超过m,那么这一半的区间里一定包含重复的数字;否则,另一半m+1-n的区间里一定包含重复的数字。继续把包含重复数字的区间一分为二,直到找到一个重复的数字。和二分查找算法很类似,只是多了一步统计区间里数字的数目。
int countRange(const int* numbers, int length, int start, int end){
    if(numbers == nullptr)
        return 0;
    int count = 0;
    for(int i=0; i < length; i++){
        if(numbers[i]>=start && numbers[i]<=end){
            ++count;
        }
    }
    return count;
}

int getDuplication(const int* numbers, int length){
    if(numbers==nullptr || length<=0)
        return -1;
    int start = 1;
    int end = length-1;
    while(end >= start){
        int middle = (end-start)>>2 + 1;
        int count = countRange(numbers, 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;
}

按照二分查找的思路,如果输入长度为n的数组,那么函数countRange()将被调用O(logn)次,每次需要O(n)的时间,因此总的时间复杂度是O(nlogn),空间复杂度为O(1).