leetcode 41 缺失的第一个正数

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

1
2

Input: [1,2,0]
Output: 3

Example 2:

1
2

Input: [3,4,-1,1]
Output: 2

Example 3:

1
2

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

• Putting every number into the right place recuritivly

  ​ 4, 3, 1, 2, 5

  -> 2, 3, 1, 4, 5 ( swap 4, 2 )

  -> 3, 2, 1, 4, 5 ( swap 2, 3 )

  -> 1, 2, 3, 4, 5 ( swap 1, 3 )

• Scan the array, find the first place that not correspond to it’s value

  ​ 1, 2, 3, 6, 7 ( return 4 )

  ​ 4, 5, 6, 7, 8 ( return 1 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

   public static void (int[] list, int a, int b){
       int temp = list[a];
       list[a] = list[b];
       list[b] = temp;
   }

public static int solution(int[] list){
       int n = list.length;
       for (int i=0; i<n; i++){
           while(list[i]>0  && list[i]<n && list[i]!= list[list[i]-1]){
               swap(list, i, list[i]-1);
           }
       }

       for (int i=0; i<n; i++){
           if (list[i]!= i+1)
               return i+1;
       }
       return n+1;
   }