LeetCode-41

发表于   |   分类于   |  

First Missing Positive

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

题目大意：

  1. 按依次顺序找到数组中第一个缺少的正整数。
  2. 时间复杂度要求为O(n),空间复杂度为O(1)

解题思路：

  1. 因为要求空间复杂度为O(1)所以，不能使用额外的空间，只能在原数组上进行处理，最先开始想到先把数组排序，再去判断，但是，现有的排序算法中没有O(n)效率，最低也只有快排，而且代码量长需要用到额外的空间。
  2. 查询discuss，其他的答案，发现他们的解法很棒。

解法有如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int firstMissingPositive(int[] A) {
       int i = 0;
       while(i < A.length){
           if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;
           else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
           else i++;
       }
       i = 0;
       while(i < A.length && A[i] == i+1) i++;
       return i+1;
   }

   private void swap(int[] A, int i, int j){
       int temp = A[i];
       A[i] = A[j];
       A[j] = temp;
   }