第一周

       First Missing Positive

           第一周 2017/9/10

题目的源地址–https://leetcode.com/problems/first-missing-positive/description/

题目描述：
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)，而且要使用恒定的空间。

---

再说自己的理解之前，先把代码放上

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int result = 1, CurrentVal, NextVal;
        int size = nums.size();
        set<int> Set;

        for (int i = 0; i < size; i++) {
            Set.insert(nums[i]);
        }

        set<int>::iterator its;
        set<int>::iterator it_temp;
        for (its = Set.begin(); its != Set.end(); its++) {
            CurrentVal = *its;
            if (CurrentVal > 0) {
                if (CurrentVal == result) {
                    if (++its != Set.end()) {
                        NextVal = *its;
                        if (CurrentVal + 1 != NextVal) {
                            result = CurrentVal + 1;
                            break;
                        } else {
                            its--;
                            if (its == Set.end()--) {
                                result = *its + 1;
                                break;
                            }
                            result++;
                        }
                    } else {
                        result = CurrentVal + 1;
                        break;
                    }   
                } else {
                    break;
                }
            }
        }

        return result;
    }
};

解决上面的问题，我自己的思路是先将无序数组变成有序，然后就可以很快地找出最小的缺失的正整数。首先题目要求时间复杂度为O(n)，这可以将平时大多数用的排序算法排除了。那么将如何对数组排序呢？我想过一个不用排序的方法，就是定义一个数组值全为0的array,然后遍历vector，将array[vector[i]]的值设为1，表示已经出现，最后只需遍历这个数组array,就可以找到最小的缺失的正整数。但因为并不知道无序数组值的范围，所以就无法声明数组，而且题目要求恒定空间，所以不能使用动态数组。即便可以，如何无序数组的值范围很大，声明的数组就会很大，遍历起来会浪费很多时间，同时也会浪费部分空间，所以我最后选择使用set。set默认是从小到大排序的，而且不重复，所以将vector的值插入到set后就可以用于比较。

在排序完后就可以遍历set，找出答案。在遍历的过程中需要比较将前一个数和后一个数比较，看看两者之间是否只相差1，如果不是，就返回后一个数的值，这是从大方向来看，但需要注意几种特殊情况：

1）数组只有一个数，如果这个数为1，就返回2，但如果这个数大于1，就返回1。
2）数组中的值是按照大小排序的，两两之间并没有间隔，那么就返回最后一个数+1。
3）如果数组的值全为非正整数，那么就返回1。

上面图片是最后的结果，从图片可以看出，虽然算法是通过了，但算法的运行时间是6ms,而我这个算法的排名是比较靠后的，我觉得这是因为使用了set的缘故，而且这个算法的圈复杂度是挺大的，所以这个题目是有更好的算法来解决，只是自己没想到，如果想到的话，自己会再重新刷一遍的。