32ms C++ solution, without the risk of overflow


  • 1
    K
    int missingNumber(vector<int>& nums) {
            int nsize=nums.size();
            int i=0;
            while(i<nsize)
                if(nums[i]!=i)
                    if(nums[i]==nsize)
                    {
                        i++;
                        continue;
                    }
                    else
                        swap(nums[i],nums[nums[i]]);
                else i++;
            for(i=0;i<nsize;i++)
                if(nums[i]!=i)return i;
            return nsize;
        }
    

    It takes two loops.
    The first one rearranges the array so that each num[i] is at the corresponding index i
    e.g [1,0,4,2] => [0,1,2,4]
    except the missing num.

    Then the second loop will find that missing num. If failed, it means the missing num is n(because n is not included in array)


Log in to reply
 

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