C++ accepted solution, TC:O(n), SC:O(1)


  • 0
    H

    First, this is my code.

    class Solution {
    private:
        vector<int> answer;
        int i, tmp,n_sz = 0;
    
    
    public:
        vector<int> findDisappearedNumbers(vector<int>& nums) {
            answer.clear();
            n_sz = nums.size()-1;
    
            if(!nums.empty())
            {
                 //swap part
                while(i <= n_sz)
                {
                    if(nums[i] != nums[nums[i]-1])                         // if the element is not in right position, swap it to place the number.
                    {
                        tmp = nums[nums[i]-1];
                        nums[nums[i]-1] = nums[i];
                        nums[i] = tmp;
                    }
                    else ++i;
                }                                               //if there is already a suitable number in the place, start from the next element.  
    
                for(i = 0; i <= n_sz; ++i)
                {
                    if(nums[i] != (i+1))                                    //if the element isn't equal to its (index+1), (the index+1) is an missing number.
                       answer.push_back(i+1);
                }
                             
            }                
                return answer;        
        }
    };
    

    Using the index from an array, and placing numbers in a place where nums[number-1]. So there will be 1 in nums[0]. Doing this over again and again, you can get a ordered array.

    However, some numbers represent twice so there will be numbers not in nums[number-1]. That's because duplicated numbers stealed rooms for numbers which is missing.

    As the result, if you check the element with the index, you can know which number is missing one.

    In this way, no matter how many times same numbers are appeared in an array, we can find every missing numbers.

    Process Example:

    INPUT : [2, 1]

    i = 0
    nums[0] = 2
    nums[nums[0]-1] = nums[2-1] =nums[1]= 1

    1 != 2, swap 1 with 2.

    result : [1,2]

    still i = 0, but nums[0] = 1 and nums[nums[0]]=nums[1-1]=nums[0]=1

    so nums[0]=nums[0], ++i.

    then i = 1, nums[1]=nums[1]. ++i.

    i = 2 > nums.size()-1, exit loop.

    processed array is [1,2]. element -1 = index of the array so nothing is happend in answer.

    OUTPUT : []


Log in to reply
 

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