My c++ solution (4 ms)


  • 31
    N
    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            for(int i=0; i<nums.size(); i++){
                if(i+1==nums[i]) continue;
                int x = nums[i];
                while(x>=1 && x<=nums.size() && x!=nums[x-1]){
                    swap(x, nums[x-1]);
                }
            }
            for(int i=0; i<nums.size(); i++){
                if(i+1!=nums[i])    return i+1;
            }
            return nums.size()+1;
        }
    };
    

    Since we can not use extra space, so thinking about using the nums vector itself to record a positive number occurred.


  • 1
    I

    What's the time complexity of the while loop nested in the for loop? Could that become quadratic? The original question insisted on O(n).


  • 0
    H

    What the while loop does is sequentially re-arrange the numbers to where they are supposed to be: number i is located in cell with index i. This is preparing for the second for loop, which have one single scan across the array and report the missing number. Considering the fact that one number cannot be re-arranged twice, all the steps taken in the while loop across all the iterations in the parent for loop are O(n).


  • 1
    L

    Similar idea in C#.

    public int FirstMissingPositive(int[] nums) {
        if(nums.Length == 0) return 1;
        for(int i = 0; i < nums.Length; i++)
            while(nums[i] >= 0 && nums[i] < nums.Length && nums[i] != i && nums[i] != nums[nums[i]])
                nums[i] = nums[i] ^ nums[nums[i]] ^ (nums[nums[i]] = nums[i]);
        for(int i = 1; i < nums.Length; i++)
            if(nums[i] != i) return i;
        return nums[0] == nums.Length ? nums.Length + 1 : nums.Length;
    }

  • 0
    S
    This post is deleted!

Log in to reply
 

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