题解 | #数组中重复的数字#

题目：数组中重复的数字

描述

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

例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1。

思路分析：在进行具体思考时，应该注意两点，当输入的数组为空时或者输入的数组不重复。这两点问题应该另外分析。

首先可以将数组进行排序，将排好序的数组，从开头进行遍历，在遍历的同时，记录好当前位置与之前位置的数，进行比较，如果相等，则输出该数，否则判断下一位数字。

具体思路分析：当输入的数组长度为7，具体数值为[2,3,1,0,2,5,3]时，进行以下分析：

排序完成后，进行遍历操作，将当前位置与之前位置的两个数进行比较，相等的话，输出该数，经过比较，输出的数字为2。

实现的具体C++代码如下所示：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        // write code here
        if(numbers.size()==0)
        {
               return -1;
           }
        sort(numbers.begin(),numbers.end());
        for(int i=0;i<numbers.size()-1;)
        {
            if(numbers[i]==numbers[i+1])
            {
                return numbers[i];
            }
            i++;
        }
        return -1;
    }
};

该算法的时间复杂度为O(n)。

思路分析：从头到尾遍历数组，当扫描到下标位为i的位置时，比较数字m是否等于i，如果是，接着扫描下一个数字，如果不是，则拿它和下标位m的数字比较，如果相等，就找到了第一个重复数字（该数字在下标i和m位置同时出现了），如果不相等，就把第i个数字和第m个数字交换，重复这个比较。

具体思路如下表所示：

第一次

第二次

第三次

第四次

第五次

当判断到4的时候，下标4代表的数字为2，跟下标为2代表的数字相同，即数字2为重复数字。

该C语言代码如下所示：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @return int整型
 */
int duplicate(int* numbers, int numbersLen ) {
    // write code here
    if(numbers == NULL || numbersLen <= 0)//非正常情况
        return -1;
    int i = 0;
    for(;i < numbersLen;i++){
        if(numbers[i] < 0 || numbers[i] >= numbersLen)//题目要求
            return -1;
    }
    for(i = 0; i < numbersLen;i++){
        while(numbers[i] != i){
            if(numbers[i] == numbers[numbers[i]])
                return numbers[i];
            int tmp = numbers[i];//数字交换
            numbers[i] = numbers[tmp];
            numbers[tmp] = tmp;
        }
    }。
    return -1;
}

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