现在的位置: 首页 > 综合 > 正文

leetcode:First Missing Positive

2019年11月03日 ⁄ 综合 ⁄ 共 882字 ⁄ 字号 评论关闭

一、 题目

给出一个未排序的数组,找出第一个丢失的正整数,

例如:给出[1,2,0] 返回3

   给出[3,4,-1,1] 返回2

注:算法O(n)的时间和常量的空间

二、 分析

一开始,我理解错误,以为是找出第一个右边比左边小的数,后来发现我想的太简单了,题目的难点在它的要求,即时空要求。我们不能使用一般的排序或重新开辟数组,所以我们只有使用数组本身,即建立数与索引的关系:A[n] = n + 1。思路:

思路一:

1、依次遍历元素,当前元素如果为负数或零或等于当前索引值加1则跳过,否则交换A[n]A[A[n]-1](如果交换的这两个数相等则应特殊处理,不然会死循环,直接跳过即可)

2、如果不符合1则向右移动索引,直到完成;

3、再次遍历数组,找出第一个不符合A[n] = n + 1的数返回 n+1

4、如果元素全部符合,则返回 n + 1;

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
    	int i = 0;
        while(i!=n){
        	if(A[i]>0&&A[i]!=A[A[i]-1]&&A[i]<=n){
        		swap(A[i],A[A[i]-1]);
        	}
        	else 
        		i++;//直到第一个符合或者无效跳过
        }
        for (int i = 0; i < n; ++i){
        	if(A[i] != i+1)
        		return i+1;
        }
        return n+1;
    }
    int swap(int &x,int &y){
    	int temp = x;
    	x = y;
    	y = temp;
    }
};

思路二:

1、排序,从小到大;

2、从第一个不是负数或零的数起,判断是否为1-n的顺序和是否和前面的重复,不符合则返回k;

3、如果全部符合,则返回k+1;

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        if(n == 0) return 1;
    	int k = 0;
    	sort(A,A+n);
		for (int i = 0; i < n; ++i){
        	if(A[i]>0&&A[i]!=A[i-1]){
        		k++;
        		if (A[i] != k)
        			return k;
        	}
        }
        return k+1;
    }
};

抱歉!评论已关闭.