題目描述

Given an unsorted integer array, find the first missing positive integer.
For example,
Given[1,2,0]return3,
and[3,4,-1,1]return2.
Your algorithm should run in O(n) time and uses constant space.

解析：把數字放在對應的位置上，然后再遍歷，如果該位置的元素不為該位置，就返回該位置+1

例如：【3,4，-1,1】應該返回什么呢？
當i=0時候，該0位置應該放元素1，現在放的3，需要把3與位置為3-1的元素-1交換，然后數組變為了
【-1,4,3,1】，此時的i=0，但是-1不是正整數，可以不用交換了；

當i=1時候，該位置的元素為4，此時4>0,應該與4-1的位置元素交換，交換后得到了【-1,1,3,4】，此時的i=1,元素1是否應該放在i=1呢？顯然不是，元素值1應該放在位置號為1-1=0的位置上，即需要與-1交換，得到【1，-1,3,4】…
依次循環下去…

最后在遍歷數組，如果該位置的元素不等于該元素的角標+1，就返回該元素的角標+1

public class Solution {public int firstMissingPositive(int[] A) {for(int i = 0;i < A.length;i++){while(A[i] > 0 && A[i] <= A.length && A[A[i]-1] != A[i]){//該位置元素是正數，且該元素不該在該位置，交換int temp = A[A[i]-1];A[A[i]-1] = A[i];A[i] = temp;}}for(int i = 0; i < A.length;i++){//遍歷數組，如果該位置的元素值不等于該元素的索引+1，就返回該元素的索引+1if(A[i] != i+1)return i+1;}return A.length + 1;//所有的元素滿足對應的位置號，輸出下一個連續的正數} }

總結

以上是生活随笔為你收集整理的《leetcode》first-missing-positive的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。