解法一,O(N)时间复杂度,O(N)空间复杂度的方法,使用哈希来存储出现过的元素次数,如果出现次数大于2,则返回
代码如下:
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        int len=numbers.size();          
                if(len==0)
                {
            return -1;
        }
        unordered_map<int,int> num_cnt_map;
        for(int i=0;i<len;i++){
                        //判断是不是合法
            if(numbers[i]>len)
            {
                return -1;
            }
            num_cnt_map[numbers[i]]++;
            if(num_cnt_map[numbers[i]]>1)
            {
                return numbers[i];
            }
            std::cout<<num_cnt_map[numbers[i]]<<endl;
        }
      
        return -1;
    }
};

解法二,O(N)时间复杂度,和O(1)的空间复杂度
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    void swap(int &a,int &b){
        int temp=a;
        a=b;
        b=temp;
    }
    
    int duplicate(vector<int>& numbers) {
        int len=numbers.size();
        if(len==0){
            return -1;
        }
        for(int i=0; i<len;i++){
            //判断不不合法的输入
            if(numbers[i]>len)
            {
                return -1;
            }
            while(numbers[i]!=i)
            {
                if(numbers[i]==numbers[numbers[i]])
                {
                    return numbers[i];
                }
                else
                {
                    swap(numbers[i],numbers[numbers[i]]);
                }
            }
        }
      
        return -1;
    }
};


解法三: O(NlogN)时间复杂度,O(1)空间复杂度
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int count_num(vector<int> numbers,int start,int end)
    {
        int count=0;
        for(auto num:numbers)
        {
            if(num>=start&&num<=end)
            {
                count++;
            }
        }
        return count;
    }
    
    int duplicate(vector<int>& numbers) {
        int len=numbers.size();
        if(len==0){
            return -1;
        }
        int start=0;
        int end=len-1;
        while(end>=start)
        {
            int mid=(end+start)/2;
            int count=count_num(numbers, 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;
    }
};
这种类似二分方法只能过90%,因为当n是偶数,划分2边区间大小一样,2边分配个数相同,或者是每边分配的个数恰好和坐标个数相等,则无法判断