给出一个无序的整数型数组,求不在给定数组里的最小的正整数
例如:
给出的数组为[1,2,0] 返回3,
给出的数组为[4,3,-1,-2,1] 返回2.
你需要给出时间复杂度在O(n)之内并且空间复杂度为常数级的算法
//对于每个数i调整到i-1位置,当然调整后还要接着判断。 //最后重头扫一遍,发现第一个a[i]!=i+1位置的就返回i+1; class Solution { public: int firstMissingPositive(int A[], int n) { for(int i=0;i<n;i++){ if(A[i]>=1&&A[i]<=n&&A[A[i]-1]!=A[i]) swap(A[i],A[A[i]-1]),i--; } for(int i=0;i<n;i++) if(A[i]!=i+1) return i+1; return n+1; } };
public int firstMissingPositive(int[] A) { if (A == null || A.length == 0) // 防止越界 return 1; for (int i = 0; i < A.length; i++) { // A[i] - 1 < A.length 超出范围不交换 A[i] != A[A[i] - 1] 相等不交换 while (A[i] > 0 && A[i] != i + 1 && A[i] - 1 < A.length && A[i] != A[A[i] - 1]) { swap(A, i, A[i] - 1); } } for (int i = 0; i < A.length; i++) { if (A[i] != i + 1) { return i + 1; // 第一个不相等就返回 } } return A[A.length - 1] + 1; // 数组交换后是有序正数,就返回最大 + 1 } public void swap(int[] A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } }
import java.util.*; public class Solution { public int firstMissingPositive(int[] A) { if(A.length == 0 ) return 1; int tmp = 1; Arrays.sort(A); for(int i: A){ if(i>=0 && tmp >= i){ tmp= i+1; } } return tmp; } }
sort的时间复杂度是O(nlogn)...但是可以很好地插空求到需要的返回值 偷懒一时爽一直偷懒一直爽!
import java.util.ArrayList; public class Solution { /*解题思路:先将数组存入Arraylist中,因为这样遍历数组中的任何一个元素的时间变成O(1),即以空间换取时间。 步骤:(1)遍历数组,找到最大值max,并将数组存入Arraylist中,时间复杂度为O(n) (2)遍历从正整数1到最大值max之间的数,并判断Arraylist中是否包含该数。若不包含该数字,则该数字就是第一个缺失的正整数; 若循环走到底,即Arraylist包含了1到max之间所有数,则第一个缺失数字就是max后一个数字,即max+1.时间复杂度为O(n)*/ public int firstMissingPositive(int[] A) { if(A.length == 0) return 1; ArrayList<Integer> list = new ArrayList<>(); int max = 0; //步骤(1) for(int i = 0;i < A.length;i ++){ list.add(A[i]); if(A[i] > max){ max = A[i]; } } //步骤(2) for(int i = 1;i <= max;i ++){ if(!list.contains(i)) return i; } return max + 1; } }
class Solution { public: int firstMissingPositive(int A[], int n) { if(A==nullptr || n<=0) return 1; unordered_map<int,int> intMap; for(int i=0;i<n;i++) intMap[A[i]] = i; int max = *max_element(A,A+n); for(int i=1;i<=max;i++) { if(intMap.find(i) == intMap.end()) return i; } return max+1; } };
int firstMissingPositive(int* A, int n) { vector<bool> res(n,false); for(int i = 0; i < n; ++i) { if(A[i] > 0 && A[i] <= n) res[A[i] - 1] = true; } for(int i = 0; i< res.size();++i) if(res[i] == false) return i+1; return n+1; }上面最后两行,为什么是i+1,n+1,因为:下标从0开始,而最小正数从1开始。
class Solution { public: int firstMissingPositive(int A[], int n) { vector<int> v(n+1, 0); for (int i = 0; i<n; ++i) { if (A[i] <= n && A[i] >= 0) v[A[i]] ++; } for (int i = 1; i <= n; ++i) { if (v[i] == 0) return i; } return n + 1; } }; //使用hash,n个数只需要保存1-n的个数,因为如果缺少一定是在这些数中间,否则就是n+1
/* 说一下思路吧 遍历数组,如果数组的元素k范围是[1,length],与nums[k-1]的元素交换位置 处理结束,数组中i下标的元素为i+1(即指向下一元素),第一个不满足该条件的元素就是所求元素 表述起来可能有点抽象,结合代码画个图理解的更快 */ public int firstMissingPositive(int[] nums) { if (nums == null || nums.length < 1) return 1; int i = 0; while (i < nums.length) { if (nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length) i++; // 防止死循环.条件不能是else if (nums[i] != i + 1) //比如[1,1]会引起死循环 else if (nums[nums[i] - 1] != nums[i]) swap(nums, i, nums[i] - 1); else i++; } i = 0; while (i < nums.length && nums[i] == i + 1) i++; return i + 1; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
public class Solution { public int firstMissingPositive(int[] A) { if(A.length == 0) return 1; int max = Integer.MIN_VALUE; for (int i = 0; i < A.length; i ++) { max = max > A[i] ? max : A[i]; } boolean[] flag = new boolean[max + 1]; for (int i = 0; i < A.length; i ++) { if(A[i] > 0) flag[A[i]] = true; } for (int i = 1; i < flag.length; i ++) { if( ! flag[i]) return i; } return max + 1; } }
Put each number in its right place.
For example:
When we find 5, then swap it with A[4].
At last, the first place where its number is not right, return the place + 1.
class Solution {
public:
int firstMissingPositive(int A[], int n)
{
for(int i = 0; i < n; ++ i)
while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
swap(A[i], A[A[i] - 1]);
for(int i = 0; i < n; ++ i)
if(A[i] != i + 1)
return i + 1;
return n + 1;
}
};
import java.util.*; public class Solution { /** * * @param A int整型一维数组 * @return int整型 */ public int firstMissingPositive (int[] A) { int min = 1; if (A == null || A.length == 0){ return min; } Arrays.sort(A); int len = A.length; for (int i = 0; i < len; i++) { if ( A[i] == min){//找到当前值就加1 min++; } } return min; } }
int firstMissingPositive(int* A, int n) { // write code here //最终一个整数i被填写入A[i-1] //若一个位置的数不属于这,那么填充到它属于的位置,并不断下去直到 完成闭环 for(int i=0;i<n;i++) { if(A[i]==i+1) continue; int k=A[i];//其目标填充位置 while(k>0 && k-1<n && A[k-1]!=k) //注意如果k值过大 将超出范围 { int tmp=A[k-1];//记录下目标位置的值 A[k-1]=k; k=tmp; } } for(int i=0;i<n;i++) { if(A[i]!=i+1) return i+1; } return n+1; }
public int firstMissingPositive (int[] A) { int[] temp = new int[A.length]; for(int i=0;i<A.length;i++){ if(A[i] > 0 && A[i] <= A.length){ temp[A[i]-1] = A[i]; } } for(int i=0;i<temp.length;i++){ if(temp[i]==0){ return i+1; } } return A.length+1; }
public int firstMissingPositive (int[] A) { if(A == null || A.length == 0) { return 1; } for(int i = 0; i < A.length; i++) { int v = A[i]; while(v > 0 && v <= A.length && v != A[v - 1]) { swap(A, i, v - 1); v = A[i]; } } for(int i = 0; i < A.length; i++) { if(A[i] != i + 1) { return i + 1; } } return A.length + 1; } public void swap(int[] A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; }