First Missing Positive
Difficulty:Hard
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),空间复杂度是O(1).
一开始觉得数组中会有很多连续的数，所以就想对插入排序进行改进来计算，改进就是想在已经插入的数中，如果是连续的就只保存开头和结尾，比如（2,3,4,5就只用2->5来保存），整个插入排序用链表进行维护，这样每次插入要比较的数量就会少很多。
后来想想这个做法在数组中连续的数很少的情况下根本没什么优势，并不能保证复杂度都是 O(n)和空间复杂度是O(1)，不过leetcode还是给通过了，而且比70%已通过的算法都快，不知道是不是直接用插入排序也会给通过。。。
最后看了网上的解答，通过在原数组的进行交换，把数放到该放的位置上，比如数字5就与数组第5个位置的数进行交换，进行两次循环就能找出答案，我这真的太麻烦了。。。
int firstMissingPositive(vector<int>& nums) { if (nums.size() == 0)//为空返回1 return 1; list<pair<int, int>> record;//第一个int是插入的数 第二个数表示状态 0表示左右没有连续 1表示是连续数的开头 2表示连续数的结尾 int i = 0; for (; i < nums.size(); i++){//找到第一个大于0的数的位置并把数插入到record中 if (nums[i] > 0){ record.push_back(pair<int, int>(nums[i], false)); break; } } for (i=i + 1; i < nums.size(); i++){//循环生成record list<pair<int, int>>::iterator it = record.begin(); list<pair<int, int>>::iterator it_last; int k = 0; if (nums[i]>0) while (1){ if (it != record.end()){//寻找插入点 头/中间插入 if (nums[i] > it->first){//未寻找到插入点 it_last = it; it++; k++; } else{//寻找到插入点 if (k>0){//中间插入 if (it->first == nums[i] || (it_last->second == 1 && it->second == 2)) break; if ((nums[i] - it_last->first) == 1 && (it->first - nums[i]) == 1){//左右都与插入值相连 if (it_last->second >0 && it->second > 0){//当前是连续输结尾 后是连续输开头时才应该插入 if (it_last->second > it->second){ record.erase(it_last); record.erase(it); } break; } else if (it_last->second >0){ it->second = 2; record.erase(it_last); break; } else if (it->second > 0){ it_last->second = 1; record.erase(it); break; } else{ it_last->second = 1; it->second = 2; break; } } else if ((nums[i] - it_last->first) == 1){ //与左边相连 if (it_last->second >0){ record.insert(it, pair<int, int>(nums[i], 2)); record.erase(it_last); break; } else{ record.insert(it, pair<int, int>(nums[i], 2)); it_last->second = 1; break; } } else if ((it->first - nums[i]) == 1){//与右边相连 if (it->second > 0){ record.insert(it, pair<int, int>(nums[i], 1)); record.erase(it); break; } else{ it->second = 2; record.insert(it, pair<int, int>(nums[i], 1)); break; } } else{//左右都不相连 record.insert(it, pair<int, int>(nums[i], 0)); break; } } else{//头部插入 if (it->first == nums[i]) break; if ((it->first - nums[i]) == 1){ if (it->second == 0){ it->second = 2; record.push_front(pair<int, int>(nums[i], 1)); break; } else{ record.push_front(pair<int, int>(nums[i], 1)); record.erase(it); break; } } else{ record.push_front(pair<int, int>(nums[i], 0)); break; } } } } else{//末尾插入 if ((nums[i] - it_last->first) == 1){ if (it_last->second == 0){ it_last->second = 1; record.push_back(pair<int, int>(nums[i], 2)); break; } else{ record.push_back(pair<int, int>(nums[i], 2)); record.erase(it_last); break; } } else{ record.push_back(pair<int, int>(nums[i], 0)); break; } } } } list<pair<int, int>>::iterator it = record.begin(); list<pair<int, int>>::iterator it_tmp = it; bool isEnd = false; for (int j = 1; j <= nums.size()+1; j++){//查找第一个丢失的正整数 if (j != it->first){ if (j < it->first){ return j; } else{ if (it->second ==1){ it_tmp = it; it_tmp++; if (it_tmp != record.end()){ if (it_tmp->first <= j){ it++; j--; } } else{ return j; } } else if (it->second == 2){ return j; } else{ return j; } } } } return 1; }
