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 = 0; i < n; i ++) { int inx = abs(nums[i]) - 1; nums[inx] = -abs(nums[inx]); } // Pass 1 - get all positive for(int i = 0; i < n; i ++) if(nums[i] > 0) ret.push_back(i + 1); return ret; } };
LeetCode "448. Find All Numbers Disappeared in an Array"
原文：http://www.cnblogs.com/tonix/p/6254902.html