C++ Easy O(n) time and O(1) extra space solution through swapping.


  • 1
    K

    Given that each element is between 1 and n. All the elements occur either once or twice.

    So, in first pass, we can swap all the elements to their respective positions.

    In second pass, all the one-time occuring elements are supposed to be at their positions. The elements that violate this conditions are the elements of our interest (because they are at some other positions, in addition of being at their respective index, where they are not supposed to be).

    class Solution {
    public:
        vector<int> findDuplicates(vector<int>& nums) {
            if(nums.empty()) return {};
            vector<int> res;
            int n = nums.size();
            for(int i = 0; i < n; i++)
                nums[i]-=1;       //for indexing flexibility
            
            int i = 0;
            while(i < n) {
                if(nums[i] != nums[nums[i]]) 
                        swap(nums[i], nums[nums[i]]);   //swap elements to their respective indexes.
                else 
                         i++;
            }
            for(int i = 0; i < n; i++) {
                if(nums[i] != i) 
                         res.push_back(nums[i]+1);     //get the elements which are at some other indexes (as they are occuring twice)
            }
            return res;
        }
    };
    

  • 0
    O

    The same idea as yours!

    My java solution

    public List<Integer> findDuplicates(int[] nums) {
            List<Integer> res = new ArrayList<>();
            
            for (int i=0; i<nums.length; i++) {
                while (nums[i] != nums[nums[i]-1]) {
                    swap(nums, i, nums[i]-1);
                }
            }
            
            for (int i=0; i<nums.length; i++) {
                if (nums[i] != i+1) res.add(nums[i]);
            }
            
            return res;
        }
        
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    

  • 0
    U

    @Offers_Chen can u tell me why this is O(n)?


  • 0
    O

    @u.u It's like one-to-one buckets. I think the swap operation will happen at most n times. The number will check if its bucket is occupied. If so, this loop will do nothing.


  • 0
    P

    I think it is more easily to come up with this method than the flip one.


Log in to reply
 

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