C++ solution without extra space


  • 0
    S
    class Solution {
    public:
        vector<int> findDuplicates(vector<int>& nums) {
            vector<int> ans;
            for (int i = 0; i< nums.size(); ++i) if (nums[i] != -1 && nums[i] != i+1) {
                int idx = i, val = -1;
                swap(val, nums[idx]);
                for (int nxt = val-1; val != -1 && val != idx+1; idx = nxt, nxt = val-1) {
                    if (nxt+1 == nums[nxt]) ans.push_back(nxt+1);
                    swap(val, nums[nxt]);
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

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