C++ Solution with O(nlgn) Complexity


  • 0
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size() - 1, mid, count = 0;
        while( l < r ) {
            mid = ( l + r ) / 2;
            for( int i : nums ) {
                if( i <= mid && i >= l) count++;
            }
            if( count > mid - l + 1) r = mid;
            else l = l == mid ? mid + 1 : mid;
            count = 0;
        }
        return l;
    }

Log in to reply
 

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