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

题解一:暴力(TLE超时，不能AC此题)
解题思路：第一层循环依次选取一个锚点数字，第二层循环遍历剩下的数字，当找到相同的两个数字，退出循环，返回正确的结果。

复杂度分析：
时间复杂度:O(n^2),两层循环
空间复杂度:O(1)
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        // write code here
        for(int i=0;i<numbers.size()-1;++i){//第一层循环，选择锚点数字
           for(int j=i+1;j<numbers.size();++j){//第二层，匹配两数是否相等
               if(numbers[i]==numbers[j]) return numbers[i];
           }
        }
        return -1;
    }
};

题解二:排序+遍历(条件：允许修改原数组)
解题思路:
1、对数组进行排序(手写推荐:堆排序,系统函数:sort()),此步骤时间复杂度O(nlog(n));
2、遍历数组，查看相邻元素是否有相等的，有直接返回结果，此步骤时间复杂度O(n);

复杂度分析：
时间复杂度:O(nlog(n)),上面已经分析出时间复杂度
空间复杂度:O(1)
代码如下:

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

题解三:hash散列(使用空间置换时间，降低时间复杂度，目前内存技术发展迅速，用空间置换时间会更合理)
解题思路：一次循环依次遍历数组，并与查询hash表(hash表采用unordered_set容器，而不要采用set，unordered_set底层使用的vector+list开链法，理论查询时间O(1),set底层采用红黑树，查询时间稳定log(n))：
1、hash表存在该数字，结束返回结果；
2、hash表不存在该数字，将该数字加入hash表中；
循环结束代表未找到，返回-1；

复杂度分析：
时间复杂度:O(n),一层循环
空间复杂度:O(n)，最坏情况，找不到结果，hash表需要存所有的值，即需要O(n)空间存储数字
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        // write code here
        unordered_set<int> u_set;
        for(int i=0;i<numbers.size();++i){
          if(u_set.count(numbers[i])){//hash表存在
              return numbers[i];
          }else{//不存在
              u_set.insert(numbers[i]);//将该数字加入hash表中
          }
        }
        return -1;
    }
};

题解四:原地hash(再一次降低空间复杂度,并且允许修改原数组)
解题思路：利用题目的条件，题目给出的数组长度为n，并且numbers数组中的所有的数字都在0~n-1的范围内;所以可以利用swap()函数使numbers里面的数对应到数组的下标上。
遍历整个数组：
1、当numbers[i]等于下标i，判断下一个下标是否对应；
2、当numbers[i]不等于下标i
(1)numbers[i]==numbers[numbers[i]],此时对应下标i的numbers[i]已经对应，那么出现重复数字；
(2)否则swap(numbers[numbers[i]],numbers[i]);
3、遍历结束都未发现重复数字，则返回-1；
举例：
numbers[i] = a, numbers[numbers[i]]=numbers[a]=b,
通过swap()后，numbers[i]=b,numbers[numbers[i]]=numbers[a]=a;

复杂度分析：
时间复杂度:O(n),最坏情形没有重复数字，那么会以O(n)的次数两两交换直至所有numbers[i]与i对应起来。
空间复杂度:O(1)，在原数组上进行操作，未使用其他空间
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        // write code here
        for(int i=0;i<numbers.size();){
            if(i==numbers[i])++i;//当numbers[i]等于下标i，判断下一个下标是否对应；
            else {
                if(numbers[numbers[i]] == numbers[i]){
                    return numbers[i];
                }else{
                    std::swap(numbers[numbers[i]],numbers[i]);//交换使numbers[i]与下标i对应起来；
                }
            }
        }
        return -1;
    }
};