#include <stdio.h> #include <vector> using namespace std; class Solution { public: int firstMissingPositive(vector<int>& nums) { for (int i = 0; i < nums.size(); i++) { if (nums[i] <= 0) { nums[i] = -1; } } nums.push_back(-1); printf("Before "); printv(nums); printf("\n"); for (int i = 0; i < nums.size(); i++) { int start = nums[i]; while (start > 0 && start < nums.size()){ int newStart = nums[start]; nums[start] = 0; if (newStart == start) { break; } start = newStart; } printf("After i %d --- ", i); printv(nums); } printf("\nAfter"); printv(nums); for (int i = 1; i < nums.size(); i++) { if (nums[i] == 0) { return i; } } return nums.size(); } void printv(vector<int>& nums) { for (int i = 0; i < nums.size(); i++) printf("%d, ", nums[i]); printf("\n"); } }; int main() { vector<int> a = {3,4,-1,1}; Solution *s = new Solution(); printf("val is %d", s->firstMissingPositive(a)); }
Standard input is empty
Before 3, 4, -1, 1, -1, After i 0 --- 3, 0, -1, 0, 0, After i 1 --- 3, 0, -1, 0, 0, After i 2 --- 3, 0, -1, 0, 0, After i 3 --- 3, 0, -1, 0, 0, After i 4 --- 3, 0, -1, 0, 0, After3, 0, -1, 0, 0, val is 1