Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode First Missing Positive

Leetcode algorithms 第 41 题: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.

解答

找出第一个没有出现的正整数。

如果1到n这n个整数全出现,可以把他们排序放到下标分别为1-n的位置中,于是数字和下标有个对应关系。同样地,如果这n个数不全出现,也可以把已经出现的放在它们本应该的位置,即数字i放到下标为i-1的位置。于是,扫描数组的每个元素A[i],如果A[i]上的数字位置不对,则将其放到正确的位置上,即为A[A[i]-1]。当然,由于有不是1-n的数字,它们不可能有正确的位置,则这些数字的位置保持不变。

处理完成后,只需要从左到右扫描一遍数组,找到第一个位置不正确的数字,即A[i] != i + 1,则i + 1即为最终的答案。

具体代码如下:

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        if (n < 1) return 1; //没有元素,返回1
        
        for (int i = 0; i < n; )
        {
            if (A[i]<0 || A[i]>=n || A[i]==i+1 || A[i]==A[A[i]-1])
                i++; //非法数字或者数字位置正确
            else
                swap(A[i], A[A[i] - 1]);//交换到正确的位置上
        }
        
        for (int i = 0; i < n; i++)
            if (A[i] != i + 1) //位置不正确
                return i + 1;
        return n + 1; //全部位置正确
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论