首页 > 代码库 > 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.
Analysis:
The idea is to use the array itself as a table. We try put a value i on the place i-1. If the value i is out of range, i.e., <=0 || >n, then ignore it. At each position i, we check whether the A[i] is a value needed to be placed on its own position, if yes, we swap it; then we check the new A[i] again. We repeat this procedure until A[i] is a value that is out of range or the right place of value A[i] is already placed a value of A[i] (Duplicate situation), we then move the i+1 position.
Solution:
1 public class Solution { 2 public int firstMissingPositive(int[] A) { 3 int len = A.length; 4 if (len==0) return 1; 5 6 for (int i=0;i<len;i++) 7 if (A[i]!=i+1){ 8 int val = A[i]; 9 while (true){10 if (val<=0 || val>len) break;11 if (A[val-1]==val) break;12 swap(A,val-1,i);13 val = A[i];14 }15 }16 17 int res = len+1;18 for (int i=0;i<len;i++)19 if (A[i]!=i+1){20 res = i+1;21 break;22 }23 24 return res;25 }26 27 public void swap(int[] A, int i, int j){28 int temp = A[i];29 A[i]=A[j];30 A[j] = temp;31 }32 }
Leetcode-First Missing Positive
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。