数组中的重复元素题解

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;
    }
};

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;
    }
};

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;
    }
};