Data-Structure_Algorithms_Coding/firmissingint.cpp at main · Sdccoding/Data-Structure_Algorithms_Coding · 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// Given an unsorted integer array, find the first missing positive integer.

// Example:

// Given [1,2,0] return 3,

// [3,4,-1,1] return 2,

// [-8, -7, -6] returns 1

// Your algorithm should run in O(n) time and use constant space.


int Solution::firstMissingPositive(vector<int> &A) {
    int n=A.size();
    int cp=0;
    for(int i=0;i<n;i++)
    {
         if(A[i]>n||A[i]<=0)
        {
            A[i]=n+1;
        }
        else if(A[i]==n)
            cp=1;


    }
    for(int i=0;i<n;i++)
    {
        if(abs(A[i])>=n)
        {
            continue;
        }

        else
        {
            A[abs(A[i])]=-1*abs(A[abs(A[i])]);
        }
    }

    for(int i=1;i<n;i++)
    {
        if(A[i]>0)
             return i;
    }
    if(cp==1)
       return n+1;
    else
        return n;


//Had said 1st Missing Non Negative Integer
//   int n=A.size();
//   for(int i=0;i<n;i++)
//   {
//       if(A[i]<0||A[i]>=n)
//          A[i]=n;
//   }
//   for(int i=0;i<n;i++)
//   {
//       if(abs(A[i])>=n)
//           continue;
//       else
//       {
//              if(A(abs(A[i]))==0)
//              {
//                  A[abs(A[i])]=-1*n;
//                  A[0]=-1*n;
//              }

//              else
//              A[abs(A[i])]=-1*abs(A[abs(A[i])]);
//       }
//   }
//   for(int i=0;i<n;i++)
//   {
//       if(A[i]>=0)
//          return i;
//   }
//   return n;


}