首页 > 代码库 > LeetCode: First Missing Positive [040]
LeetCode: First Missing Positive [040]
【题目】
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)
【思路】
假设所给数组的长度为K,则这个数组最多可存放[1,2,3,4,5,...,k]这k个正整数。
但是,数组中会有负数、0、比k大得多的数的出现,所以说数组可以存放的整数个数小于等于k个,这也保证了数组中第一个缺失的正整数一定<=k+1
举个例子:
(1)最极端的例子:数组正好存放了[1,2,3,4,...k]这K个整数,则first missing的正整数是k+1
(2)如果此时数组中有个负数-1或者一个比K大很多的数k+100,
[-1,1,2,3,4,...,k-2,k-1],[1,2,3...,k-1,k+100]
此时第一个缺失的正整数即为k-1
有了“长度为k的数组,第一个缺失的正整数一定<=k+1”的保证之后,我们就可以把数组中的整数放到对应的位置上去,比如1->A[0], 2->A[1], .... k->A[k-1]上,没有整数填充的位置用-1填充。这样的话,第一个缺失的正整数就是第一个值为-1位置对应的整数值。
【代码】
class Solution { public: int firstMissingPositive(int A[], int n) { //把<=0或者>n的位置都置成-1 for(int i=0; i<n; i++){ if(A[i]<=0||A[i]>n)A[i]=-1; } //把正整数放置到对应的位置上 for(int i=0; i<n; i++){ if(A[i]>0){ while(A[i]>0 && i!=A[i]-1 && A[A[i]-1]!=A[i]){ int temp=A[i]; A[i]=A[temp-1]; A[temp-1]=temp; } if(A[A[i]-1]==A[i] && i!=A[i]-1)A[i]=-1; //如果某些位置上的值重复出现,则需要特殊处理(加入去重处理),例如输入样例[1,1] } } //扫描第一个值<0的位置 for(int i=0; i<n; i++){ if(A[i]<0)return i+1; } return n+1; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。