首页 > 代码库 > 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.
分析:
这道题很有难度,因为要求O(n)的时间复杂度和O(1)的空间复杂度。如果不要求O(1)的空间复杂度,我们完全可以用一个大小为n的vector<bool>记录1到n数字的出现情况,然后得知the first positive integer。如果要求O(1)的时间复杂度那怎么办呢?既然这样,我们就要利用原来数组A了,对于constant space的数组问题,swap操作是个神器。我们可以把数组A中介于1到n之间的数i放到A[i-1]的位置,然后扫描数组A,如果A[i-1]不等于i,则可以找到the first missing positive integer。关于时间复杂度,因为我们每次swap总把一个介于1到n的数放到其应该的位置,所以swap n次后便结束了整个位置调整操作,可得位置调整的时间复杂度是O(n);完成位置调整后,扫描数组的操作时间复杂度也为O(n),所以总的时间复杂度为O(n)。代码如下:
1 class Solution { 2 public: 3 int firstMissingPositive(int A[], int n) { 4 bucket_sort(A, n); 5 6 for(int i = 0; i < n; i++) 7 if(A[i] != i+1) return i+1; 8 9 return n+1;10 }11 12 void bucket_sort(int A[], int n){13 for(int i = 0; i < n; i++){14 while(A[i] != i+1){15 if(A[i] <=0 || A[i] > n || A[i] == A[A[i]-1])16 break;17 swap(A[i], A[A[i]-1]);18 }19 }20 }21 };
Leetcode:First Missing Positive
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。