首页 > 代码库 > Leetcode | First Missing Positive

Leetcode | 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.

在原数组上做交换,把每个正数放到正确的位置上。因为是求正数。所以0这个位置上放的应该是1. 

1.如果A[i]==i+1,已经放在正确的位置上了,那么可以处理下一个数;

2. 如果A[i]不在[1,n]这个范围内,也不用处理,放在那里就行;

3. 如果A[i]==A[A[i]-1],也就是说,在该位置上已经有正确的数了,A[i]这个是重复的,那么也不用处理;

4. 然后就是交换A[i]和A[A[i]-1],交换一次,A[i]是放到正确的位置了,可是当前交换过来的数(原先的A[A[i]-1])可能不在正确的位置上,这个数也要处理,否则因为i向前,这个数永远也不会被正确放置了。所以这里i不能向前,直到交换之后A[i]不能再动了。所以这里要先i--,再i++。

 1 class Solution {
 2 public:
 3     int firstMissingPositive(int A[], int n) {
 4         for (int i = 0; i < n; ++i) {
 5             if (A[i] == i + 1) continue;
 6             if (A[i] < 1 || A[i] > n) continue;
 7             if (A[i] == A[A[i] - 1]) continue;
 8             swap(A[i], A[A[i] - 1]);
 9             --i;
10         }
11         for (int i = 0; i < n; ++i) {
12             if (A[i] != i + 1) return i + 1;
13         }
14         return n + 1;
15     }
16 };