leetcode 41 缺失的第一个正数
z
 2018-08-08 10:08:30  

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 swap(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;
   }