面试题3：数组中重复的数字

题目：在一个长度为的数组里的所有数字都在到的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组，那么对应的输出是重复的数字或。

测试用例：

• 长度为的数组中包含一个或者多个重复的数字；
• 数组中不包含重复的数字；
• 输入无效数组（空数组；长度为n的数组中包含到之外的数字）。

解决思路：
重排数组，通过比较交换发现重复的数字。
代码实现：

#include <cstdio>
// 参数:
//        numbers:     一个整数数组
//        length:      数组的长度
//        duplication: (输出) 数组中的一个重复的数字
// 返回值:             
//        true  - 输入有效，并且数组中存在重复的数字
//        false - 输入无效，或者数组中没有重复的数字
bool duplicate(int num[], int len, int* dup){
    if(num==nullptr || len<=0)
        return false;
    for(int i=0; i<len; i++)
        if(num[i]>=len)
            return false;
    for(int i=0; i<len; i++){
        while(num[i]!=i){
            if(num[i]==num[num[i]]){
                *dup = num[i];
                return true;
            }
            int temp = num[i];
            num[i] = num[temp];
            num[temp] = temp;
        }
    }
    return false;
}

void test(int numbers[], int lenNumbers){
    int dup;
    bool inputValid = duplicate(numbers, lenNumbers, &dup);
    if(inputValid){
        printf("There is duplicate Number in the array: %d", dup);
    }else{
        printf("There is not duplicate Number in the array.");
    }
}

性能分析：
时间复杂度为：
空间复杂度为：

扩展：不修改数组找出重复的数字。在一个长度为的数组里的所有数字都在到的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为的数组，那么对应的输出是重复的数字或。

测试用例：

• 长度为的数组中包含一个或者多个重复的数字；
• 数组中不包含重复的数字；
• 输入无效数组（空数组）。

解决思路：
采用二分查找算法的思路。

代码实现：

#include <cstdio>
// 参数:
//        numbers:     一个整数数组
//        length:      数组的长度
// 返回值:             
//        正数  - 输入有效，并且数组中存在重复的数字，返回值为重复的数字
//        负数  - 输入无效，或者数组中没有重复的数字
int countRange(const int* numbers, int length, int start, int end);

int getDeplication(const int* numbers, int length){
    if(numbers==nullptr || length <= 0)
        return -1;
    
    int start = 1;
    int end = length - 1;
    while(end>=start){
        int mid = ((end - start) >> 1) + start;
        int count = countRange(numbers, length, start, mid);
        if(start==end){
            if(count>1)
                return start;
            else
                break;
        }
        if(count>(mid-start+1))
            end = mid;
        else
            start = mid + 1;
    }
    return -1;
}

int countRange(const int* numbers, int length, int start, int end){
    if(numbers==nullptr || length <= 0)
        return 0;  
    int count = 0;
    for(int i=0; i<length; ++i){
        if(numbers[i]>=start && numbers[i]<=end)
            ++count;
    }
    return count;
}

void test(int numbers[], int lenNumbers){
    int dup = getDeplication(numbers, lenNumbers);
    if(dup<0){
        printf("There is not duplicate Number in the array.");
    }        
    else
        printf("There is duplicate Number in the array: %d", dup);
}

性能分析：
时间复杂度为：
空间复杂度为：