C++ in-space solution easy to understand (beats 95.15%)


  • 0
    G

    Explanation:
    swap each item to the location (value-1)
    For example, if the value is 1, swap it to nums[0].
    If there is already the right value in the location, it means the number appear twice and just set it to zero.

    After the first iteration finish, find all the location which is not contain the right number, which means the number is disappeared.
    (Actually these locations will contain zeros.)

    class Solution {
    public:
        vector<int> findDisappearedNumbers(vector<int>& nums){
            vector<int> ans(0);
            for(int i=0;i<nums.size();++i){
                while(nums[i]!=(i+1) && nums[i]!=0){
                    if(nums[i] != nums[nums[i]-1]) {
                        swap(nums[i],nums[nums[i]-1]); //send the number to the right place
                    } else { //Oops! duplicated!
                        nums[i] = 0;
                    }
                }
            }
            for(int i=0;i<nums.size();++i){
                if(nums[i]!=(i+1)) //may compared with zero
                    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.