C++ O(N) runtime constant space.


  • 0
    G
    class Solution {
    public:
        int missingNumber(vector<int>& nums) 
        {
            for(int i = 0; i < nums.size(); ++i)
            {
                //
                // Swap numbers until they are either in the correct position or 
                // The number does not fit in the array's range
                //
                while(nums[i] != i && nums[i] < nums.size())
                {
                    swap(nums[i],nums[nums[i]]);
                }
            }
            
            int i = 0;
    
            //
            // Find the first number that is not in its correct position
            //
            for(; i < nums.size(); ++i)
            {
                if(nums[i] != i)
                {
                    break;
                }
            }
            
            return (i);
        }
    };
    

Log in to reply
 

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