C++_O(n), in-place swap


  • 2

    This question is very similar like: 448. Find All Numbers Disappeared in an Array

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

  • 0
    Z

    Good solution


  • 0

    So smart! Thank You!
    Each swap operation puts a number to it's right place, so it's O(n) in time。


Log in to reply
 

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