C++ solution using O(n) time and O(1) space


  • 1
    L
    int missingNumber(vector<int>& nums) {
            int i=0;
            while(i<nums.size()){
                int v = nums[i];
                if (v<nums.size() && v != nums[v])
                    swap(nums[i], nums[v]); // put v on its right position
                else
                    i++;
            }
            int k = 0;
            while(k<nums.size()){   // scan the array, find the position with nums[k]!=k
                if (k != nums[k])   break;
                k++;
            }
            return k;
        }

Log in to reply
 

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