First missing positive C++ solution


  • 0
    X
    //first missing positive
    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int n = nums.size();
            int i = 0;
            while (i < n) {
                if ( (nums[i] < 1 || nums[i] > n) || nums[i] == i + 1 || nums[i] == nums[nums[i] - 1] ) {
                    i++; continue;
                }
                //else swap nums[i] and nums[nums[i]-1]
                swap(nums[i], nums[nums[i] - 1]);
            }
            
            for (i = 0; i < n; i++) {
                if (nums[i] != i + 1)
                    return i + 1;
            }
            return n + 1;
        }
        
        void swap(int& a, int& b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
    };

  • 0
    D

    What happen if I have [10,7,9] as input? or [10,7,9] is not a valid input?


Log in to reply
 

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