My first reaction is to have an unlimited length of bit-array, to mark existence. But if no extra mem is allowed, we can simply use 'sign' on each index slot to mark the same info.. it is a common technique.
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> ret;
int n = nums.size();
if(!n) return ret;
// Pass 1 - use sign to mark existence.
for(int i = ; i < n; i ++)
{
int inx = abs(nums[i]) - ;
nums[inx] = -abs(nums[inx]);
}
// Pass 1 - get all positive
for(int i = ; i < n; i ++)
if(nums[i] > )
ret.push_back(i + );
return ret;
}
};