C++_Time: O(n) Space: O(1)


  • 3

    I use in-place change and the index of vector is from 0 -> n-1.

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

  • 0

    @jasonshieh Make a little improve to use one loop to finish count sort job. :)

    int i = 0;
    while (i < nums.size()) {
        if (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);
        else ++i;
    }
    

Log in to reply
 

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