LeetCode/FirstMissingPositive.cpp at master · royalpranjal/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    void swap(int &a, int &b){
        int temp = a;
        a = b;
        b = temp;
    }

    void makeCorrect(vector<int>& nums, int index){
        int i = index;
        while(nums[i] != i+1 && nums[i] > 0 && nums[i] <= nums.size()){
            if(nums[i] != nums[nums[i]-1]){
                swap(nums[i], nums[nums[i]-1]);
            }
            else{
                break;
            }
        }
    }

    int firstMissingPositive(vector<int>& nums) {

        int i = 0;

        while(i < nums.size()){
            if(nums[i] != i+1){
                makeCorrect(nums, i);
            }
            i++;
        }

        i = 0;

        while(i < nums.size()){
            if(i+1 != nums[i]){
                return i+1;
            }
            i++;
        }

        return nums.size()+1;
    }
};