O(n) time, no extra space, C++ code.


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

Log in to reply
 

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