Sharing my 4ms C++ solution


  • 2
    T
    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int i, n = nums.size();
            for(i=0; i<n; i++)
            {
                while(nums[i]>=1 && nums[i]<=n && nums[i]!=nums[nums[i]-1])
                    swap(nums[i], nums[nums[i]-1]);
            }
            
            int j=1;
            for(j=1; j<=n; j++)
                if(nums[j-1]!=j)
                    break;
                    
            return j;
        }
    };

  • 0
    C

    Is it a O(n) Solution?


  • 0
    G

    I think it's O(n).
    In the while loop,each time we should either put a number at it's right place or skip an improper number, and there're at most n positive number to be put at the right position.


  • 0
    Y

    The worst case is swap n times in the first loop. So for the first loop, it's O(2n), and the total time is O(3n). So it is a O(n) solution.


Log in to reply
 

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