首页 > 代码库 > 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.
解题思路：数组总共有n个数，若都是连续的，最大的数是n，也就是说返回的值最大为n+1，遍历数组，如果当前的数num[i]，
如果num[i]<=0或者num[i]超过了n，则第一个丢掉的整数必然在num[i]的前面，将num[i]和num[n-1]互换，n--；
如果1<=num[i]<=n,表明这个数可能是好的，将他放在正确的位置swap(num[i],num[num[i]-1])
如果num[i]==i+1,则表明该数字在正确的位置，i++
class Solution {public: int firstMissingPositive(int A[], int n) { int m = n; for(int i=0;i<m;i++) { if(A[i] == i+1)continue; else { if(A[i] > m || A[i] == 0 || A[i] < 0 || A[i] <= i) { if(i==m-1) return m; swap(A[i],A[m-1]); m--; i--; } else { if(A[i] == A[A[i]-1]) { swap(A[i],A[m-1]); m--; i--; } else { swap(A[i],A[A[i]-1]); i--; } } } } return m+1; }};
LeetCode First Missing Positive
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。