My nlogn C solution


  • 0
    D
    int fdb(int* nums, int numsSize, int start, int end)
    {
    if(end == start){
        return start;
    }
     int n = (end+start) / 2;
    int i;
    int cs=0, cb=0;
    for(i = 0; i < numsSize; i++){
        if(nums[i] > n && nums[i] <= end){
            cb++;
        }else if(nums[i] <= n && nums[i] >= start){
            cs++;
        }
    }
    if(cs > cb){
        return fdb(nums, numsSize, start, n);
    }else{
        return fdb(nums, numsSize, n+1, end);
    }
    }
    int findDuplicate(int* nums, int numsSize) {
        return fdb(nums, numsSize, 1, numsSize-1);
    }

Log in to reply
 

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