[LeetCode]First Missing Positive

题意：在乱序数组中找到第一个没出现的正整数思路1： 直接暴力解决，复杂度O（N*N）代码1： public int firstMissingPositive1(int[] A) {// big O(N*N)if(A.length == 0)return 1;int i = 1;while(i <= A.length){boolean isfind = false;for(int j = 0; j< A.length; ++j){if(A[j] == i){isfind = true;break;}}if(!isfind) break;i ++;}return i;}思路2：先排序，，然后遍历，复杂度（N*log(N)）代码： public int firstMissingPositive2(int[] A) {//sort First O(N*log(N))+O(N)if(A.length == 0)return 1;Arrays.sort(A);int currNotFind = 1, i = 0;while(i <= A.length){if(currNotFind == A[i]){currNotFind ++ ;i++;}else if(currNotFind < A[i]){return currNotFind ;}else {i ++;}}return currNotFind;}思路3：开辟一个n个元素的数组空间，然后记录对应的数是否存在，空间和时间复杂度都是O(N)代码： public int firstMissingPositive3(int[] A) {//O(N) and O(N)spaceif(A.length == 0)return 1;int [] find = new int[A.length + 1];for (int i =0; i < A.length; ++i){if(A[i] > 0 && A[i] <= A.length){find[A[i]-1] = 1;}}for (int i = 0; i <= A.length; ++i){if(find[i] == 0)return i+1;}return 1;}

思路4：不开劈额外空间，但是这需要在元数组中进行置换，将元素i放到数组中的i-1的位置上去，空间复杂度O（1），时间复杂度O（N）代码： public int firstMissingPositive(int[] A) {//O(N) and O(1)if(A.length == 0)return 1;int temp =0;for (int i =0; i < A.length;){if(A[i] != (i+1) && A[i] >= 1 && A[i] <= A.length && A[A[i]-1] != A[i]){temp = A[i];A[i] = A[temp – 1];A[temp-1] = temp;}else ++i;}int i = 0;for (i = 0; i < A.length; ++i){if(A[i] != i+1)return i+1;}return A.length + 1;}

最好的感觉就是你什么都跟我说。