LeetCode 题解（7）：First Missing Positive

本文主要是介绍LeetCode 题解（7）：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时，与当前值-1位置的值交换（如果当前值小于0，或者大于n时，不交换）。交换后，修改数组索引，使之仍指向此位置。一次遍历结束后进行第二次遍历，如果当前值不等于当前位置+1，当前位置+1即为第一个缺失的整数。

class Solution {
public:int firstMissingPositive(int A[], int n) {if(A == NULL || n < 1)return 1;for( int i = 0; i < n; i++ ){if(A[i] != i + 1 && A[i] > 0 && A[i] <= n){//Only swap when the two values are not equal.if(A[i] != A[A[i]-1]){swap(A[i], A[A[i]-1]);i--;}}}int j;for( j = 0; j < n; j++ ){if(A[j] != j + 1)break;}return j + 1;}
};

这篇关于LeetCode 题解（7）：First Missing Positive的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---