does my C++solution meet the requirement of runtime complexity?


  • 0
    Y
    class Solution {
    public:
        int findDuplicate(vector<int>& v) {
    	if(v.size()<1) return 0;
    	if(v.size()<3) return v[0];
    	int big=v.size()-1, small=1;
    	while(big!=small){
    		int mid=(big+small+1)/2;
    		int nums=0, numb=0, numm=0;//count less than,bigger than, and equal to middle
    		for (int i=0; i<v.size(); i++){
    			if(v[i]>mid&&v[i]<=big){
    				numb++;
    			} else if(v[i]>=small&&v[i]<mid){
    				nums++;
    			} else if(v[i]==mid){
    				numm++;
    			}
    		}
    		if(numm>1) 
    			return mid;
    		if(nums>numb)
    			big=mid-1;
    		else 
    			small=mid+1;
    	}
    	return small;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.