Sorted based solution, O(1) space, O(n) time, and short proof


  • 0
    F

    Idea: place current element into the place it belongs to, whenever, current element, e, is not equal to element array[e-1] and e is not placed in array[e-1], then keep swapping the elements in those two places. After iterator all elements in the array, all elements should be in place it belongs to, then use another pass to collect missing element.

    Simple proof: loop invariant is that, whenever, loop while(nums[i] != nums[nums[i]-1] && nums[i] != i + 1) {...} is executed, it always gives that previous nums[I] in its place nums[nums[i]-1], whenever the loop condition is not true, we always have nums[i] != nums[nums[i]-1] which you cannot find current nums[I]'s place anymore, then this element is the one duplicated. With this invariant, after outer loop done, all elements should be in its place(which is nums[i] != i + 1), except for dup elements. Finally one more pass will find then (simple pass).

    Code as follow:

    vector<int> findDisappearedNumbers(vector<int>& nums) {
    		vector<int> ans;
            for(int i = 0; i < nums.size(); ++i) {
                while(nums[i] != nums[nums[i]-1] && nums[i] != i + 1) {
                    swap(nums[i], nums[nums[i]-1]);
                }
            }
            for(int i = 0; i < nums.size(); ++i) {
                if(nums[i] != i+1) {
                    ans.push_back(i+1);
                }
            }
            return ans;
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.