A different but very interesting C++ method...Expected O(n) solution...


  • 0
    P
    I set a mark number k to record the position. And we use several times of swapping to make the number set at its position as many as possible.  Because the numbers are smaller than n so if we make every different number seated in the proper order, the unmatched positions left are the numbers having not appeared.The code is shown as follows, which may show the details:
    
    public:
        vector<int> findDisappearedNumbers(vector<int>& nums) {
            int n, k, s;
            n = nums.size();
            vector<int> vec;
            k = 1;
            s = 0;
            while (k <= n)
            {
                if (nums[k - 1] == k)
                {
                    s++;
                    k++;
                }
                else
                {
                    int temp;
                    temp = nums[k - 1];
                    if (nums[temp - 1]!=temp)
                    {
                        nums[k - 1] = nums[temp - 1];
                        nums[temp - 1] = temp;
                    }
                    else
                        k++;
                }
            }
            for (int i = 1; i <= n; i++)
            {
                if (nums[i - 1] != i)
                   vec.push_back(i);
            }
            return vec;
        }
    };```

Log in to reply
 

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