Another idea using "First Missing Positive" idea

  • 0

    We can use same approach as in 41. First Missing Positive. We should place every number on it's index.
    After that, we need just to go one more time and append to result array all such numbers, that they are not equal to their indices(nums[i] != i + 1)

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

    This approach can be useful when we are using unsigned, or maximal value of array can't be greater than n.

Log in to reply

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