O(n) C++ solution


  • 0
    A

    Each element of the array is bound to exist between the index range of the array. If the element is not at its index, swap this element, say a[i], with the element at its index location which is a[a[i]]. If a[i] equals a[a[i]], the element has occurred before. The idea was borrowed from this solution to problem: https://leetcode.com/problems/first-missing-positive/

    class Solution {
    public:
    	vector<int> findDuplicates(vector<int>& nums) {
    		int i = 0;
    		set<int> answer;
    		while (i<nums.size()) {
    			if (nums[i]-1 == i) {
    				i++;
    			} else {
    				if (nums[i] != nums[nums[i]-1]) {
    					int temp = nums[i];
    					nums[i] = nums[nums[i]-1];
    					nums[temp-1] = temp;
    				} else {
    					answer.insert(nums[i]);
    					i++;
    				}
    			}
    		}
    		vector<int> vec;
    		copy(answer.begin(), answer.end(), back_inserter(vec));
    		return vec;
    	}
    };

Log in to reply
 

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