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

#include <unordered_set>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) 
    {
        int n=numbers.size();
        if(n==0 ) return -1;
        for(int i=0;i<n;i++)
        { if(numbers[i]<0||numbers[i]>=n)   //判断输入是否合法
           return -1;
        }

        unordered_set<int> uset;
        
        for(int i=0;i<n;i++)
        {
            if(uset.count(numbers[i])) return numbers[i];
            uset.insert(numbers[i]);
        }
       
        return -1;
    }
};

遍历数组中的每个元素，将其加入 unordered_set 中。如果在加入的过程中发现该元素已经存在于 unordered_set 中，说明该元素是重复的，直接返回该元素即可。

该算法的时间复杂度为O(n)，空间复杂度为O(n)，与使用数组或哈希表的方法相同。

可以在原数组上进行修改。遍历数组中的每个数字，将其对应的下标上的数字取相反数。如果一个数字被访问到时发现它的对应下标上的数字已经是负数了，说明该数字重复。

#include <unordered_set>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) 
    {
        int n=numbers.size();
        if(n==0 ) return -1;
        for(int i=0;i<n;i++)
        { if(numbers[i]<0||numbers[i]>=n)   //判断输入是否合法
           return -1;
        }

  
        
        for(int i=0;i<n;i++)
        {
           int index=abs(numbers[i]);
           if(numbers[index]<0) return index;
           numbers[index]=-numbers[index];
        }
       
        return -1;
    }
};