We can use same approach as in 41. First Missing Positive. We should place every number on it's index.
After that, we need just to go one more time and append to result array all such numbers, that they are not equal to their indices(
nums[i] != i + 1)
vector<int> result; for(int i = 0; i < nums.size(); i++) while(nums[i] != i + 1 && nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]); for(int i = 0; i < nums.size(); i++) if(nums[i] != i + 1) result.push_back(i + 1); return result;
This approach can be useful when we are using
unsigned, or maximal value of array can't be greater than