Java solution, no extra space, O(n) runtime


  • 0
    D

    My idea is simple, because we have the pre-condition that 1 <= nums[i] <= n, so for each entry num[i], we put it on its corresponding bucket nums[nums[i] - 1], if we detect that before swap, nums[i] is equal nums[nums[i] - 1], that means they are duplicates.

    public class Solution {
        public List<Integer> findDuplicates(int[] nums) 
        {
            List<Integer> res = new ArrayList<>();
            
            for (int i = 0; i < nums.length;)
            {
                // pre: 1 <= nums[i] <= n
                int k = nums[i] - 1;
                if (nums[i] != -1 && k != i)
                {
                    // swap nums[i] with nums[k]
                    int tmp = nums[k];
                    // if we find nums[i] == nums[k]
                    // that means we find duplicates
                    if (tmp == nums[i]) 
                    { 
                        res.add(nums[i]); 
                        // set -1 means this entry has duplicates
                        nums[i] = -1; 
                        i++;
                    }
                    else
                    {
                        nums[k] = nums[i];
                        nums[i] = tmp;
                    }
                }
                else
                {
                    i++;
                }
            }
            
            return res;
        }
    }
    

Log in to reply
 

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