C++ O(n) without extra space


  • 0
    Y

    Without extra space, we can use the nums vector space to mark the exist numbers.
    Because all numbers are from 1 to nums.size(), we can use swaps to make sure nums[x-1] == x.
    It's easy to proof that each number will be swap at most one time, so the runtime is O(n).

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

Log in to reply
 

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