首页 > 代码库 > Submission Details [leetcode] ---- inplace 线性时间 的两种思路
Submission Details [leetcode] ---- inplace 线性时间 的两种思路
两种思路都利用了输入的数组A，若A中存在i，则给A[i]作为标记。
因为A中的n个元素存在>n和<=0的，所以第一个缺失的正整数一定在[1-n+1]之间。
第一种思路是将标记设为一个特定的数。因为改变数值会影响该位置原来存的值，所以需要在一个循环里依次处理所有“原来的值”。
例如数组为{2,3,4,1}。对第一个数2，我们将位置(2-1)=1标记为-MAX_INT,数组变为{2,-MAX_INT,4,1}，丢失了3，所以应记录下数组原来的值，并继续将位置(3-1)=2标记为-MAX_INT。。。
int firstMissingPositive(int A[], int n) {
for (int i = 0; i < n; i++)
{
int k = A[i];
while (k > 0 && k <= n)
{
int temp = A[k-1];
A[k-1] = - INT_MAX;
k = temp;
}
}
for (int i = 0; i < n; i++)
if (A[i] != -INT_MAX)
return i + 1;
return n + 1;
}第二种思路，我们标记时可以不用改变数值，所以可以取消掉for里面的while循环。
如果不改变数值，我们能改变什么那？我们可以改变符号。这种思路里，数组中一开始存在的负数会对最终结果产生影响，所以我们做一个预处理----将所有负数变成一个大于n的数----INT_MAX。
int firstMissingPositive(int A[], int n) {
for (int i = 0; i < n; i++)
{
if (A[i] <= 0) A[i] = INT_MAX;
}
for (int i = 0; i < n; i++)
{
int k = abs(A[i]);
if (k <= n)
A[k-1] = - abs(A[k-1]);
}
for (int i = 0; i < n; i++)
if (A[i] > 0)
return i + 1;
return n + 1;
}两种方法的时间复杂度都是O(n)，准确的说，是最坏的情况下都会遍历数组3遍。
Submission Details [leetcode] ---- inplace 线性时间 的两种思路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。