[LeetCode] First Missing Positive
LeetCode First missing
2023-09-11 14:17:25 时间
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.
思路:新建一个数组B,然后用A[i]的值作为B的index,即B[A[i]] =1,然后遍历一遍B,寻找B[i]!=1的index,不过貌似我的时间复杂度是O(n),空间也是O(n)啊。。
class Solution { public: int firstMissingPositive(int A[], int n) { vector<int> B; B.resize(n + 1); //cout << "n\t" << n << endl; //printArray(A, n); for(int i = 0; i < n; i++) { if(A[i] <= n && A[i] >0) { // do A[i]'s value as B's index B[A[i]] = 1; } } //printVector(B); for(size_t i = 1; i < B.size(); i++) { if(B[i] != 1) return i; } return n+1; } };
为了实现O(n)的空间复杂度,只能使用数组A自身的空间,A[i]保存i+1,不停的交换,具体看注释吧,我觉得写的挺清楚的。。
class Solution { public: #if 0 int firstMissingPositive(int A[], int n) { vector<int> B; B.resize(n + 1); //cout << "n\t" << n << endl; //printArray(A, n); for(int i = 0; i < n; i++) { if(A[i] <= n && A[i] >0) { // do A[i]'s value as B's index B[A[i]] = 1; } } //printVector(B); for(size_t i = 1; i < B.size(); i++) { if(B[i] != 1) return i; } return n+1; } #endif int firstMissingPositive(int A[], int n) { int i = 0; int tmp; // A[i] should store (i + 1) // it means A[0] stores 1, A[1] stores 2, ... while(i < n) { // A[0~n-1] only can store 1~n; // A[i] should store i + 1 // A[i] != i +1 menas A[i] should be move to others, but A[i] should be moved where? // A[i] should be move to A[i]-1 // i.e.: {3, 1, 4, -1} // A[0]= 3, != (0+1), so 3 shoule be moved. moved to A[0] -1 =2, then check if A[2] and A[0] are equal. // so swap 3 and 4, then the array is {4, 1, 3 , -1} // but 4 also doesn't appear at A[0], so go on to swap, until the condition doens't meet, then i++ if(A[i] <= n && A[i] >0 && A[i] != (i+1) && A[A[i] - 1] != A[i] ) { tmp = A[i]; A[i] = A[tmp - 1]; A[tmp - 1] = tmp; } else i++; } //printArray(A, n); for(int i = 0; i < n; i++) { if(A[i] != (i+1) ) return i + 1; } return n+1; } };
相关文章
- [LeetCode] Palindrome Number & Valid Palindrome - 回文系列问题
- [LeetCode] First Bad Version - 二分查找
- Java实现 LeetCode 766 托普利茨矩阵(暴力)
- Java实现 LeetCode 673 最长递增子序列的个数(递推)
- Java实现 LeetCode 204 计数质数
- Java实现 LeetCode 52 N皇后 II
- Java实现LeetCode_0028_ImplementStrStr
- Java实现LeetCode_0028_ImplementStrStr
- (LeetCode 41)First Missing Positive
- LeetCode: 221_Maximal Square | 二维0-1矩阵中计算包含1的最大正方形的面积 | Medium
- (LeetCode 41)First Missing Positive
- LeetCode(117):填充同一层的兄弟节点 II
- LeetCode(86):分隔链表
- Leetcode学习计划之动态规划入门day7(1014,121,122)
- leetcode 377. 组合总和 Ⅳ----动态规划之双重for循环变式----求排列数
- leetcode - First Missing Positive
- 【LeetCode】128. 最长连续序列