# 超出向量限制，但无法确定位置。向量超出范围

``````// Find smallest missing positive number
// Solve in O(n) time and O(1) space
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:

void swap(int* a, int* b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}

// move all non positive numbers to the left side of the vector
int negativeToLeft(vector<int>& v){ // better name is seggregate!

int j=0, i;

for(int i = 0; i < v.size(); i++){
// If number is negative then swap to left side of array
if(v[i] <= 0){
swap(&v[i], &v[j]);
j++;
}

}
// return the index from where the positive numbers start
return j;
}

int firstMissingPositive(vector<int>& nums) {

// move non positive to left
int index = negativeToLeft(nums);

// find the size of the positive segment of the vector
int size = nums.size() - index;

// traverse the vector
for(int i = index; i < nums.size(); i++){

// mark the index of the number as negative, if the number is within size
if(nums[i] <= size){
nums[abs(nums[i])] = -1 * nums[abs(nums[i])];
}
}
if(index==0){
nums[0] = -1;
}

for(int i = index; i < nums.size(); i++){
// if the number at the index is positive then return the the index
if(nums[i]>0){
return i;
}
}

return size + 1;
}
};

int main()
{
vector<int> g1{-1, -2, -3, -4};

Solution m;
cout << m.firstMissingPositive(g1);
}
``````