Share my C++ without swapping and nested loop


  • 0
    Z
    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int maxV = nums.size(); // all vals should be in [1, maxV]
            int minV = maxV + 1;
            for(auto &v : nums) {
                if (v <=0 || v > maxV)
                  v = 1; // invalid num changed to 1, but not used for minV
                 else
                   minV = min(minV, v);
            }
            if (minV != 1)
              return 1;
             for(auto v : nums) {
                 // if v > maxV, it's position is marked and it's orig val is (v - maxV)
                 auto idx = ((v <= maxV) ? v : v - maxV) - 1;
                 if (nums[idx] <= maxV)
                   nums[idx] += maxV;
             }
             for(int i = 0; i < maxV; ++i)
               if (nums[i] <= maxV)
                 return i+1;
             return maxV + 1;
        }
    };

Log in to reply
 

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