Java Solution using Swap, O(n) time and O(1) space


  • 1
    M
    public class Solution {
        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> result = new ArrayList<Integer>();
            int i = 0;
            
            while(i < nums.length ){
                // if current number i is not at the position i + 1
                // or current number is not equal to nums[current - 1]
                // we do swap
                if(nums[i] != i+1  && nums[i] != nums[nums[i]-1] ){
                    int temp = nums[i];
                    nums[i] = nums[temp -1];
                    nums[temp - 1] = temp;
                }
                else{
                    i++;
                }
            }
     
            for(i = 0 ; i < nums.length; i++){
                if(nums[i] != i+1){
                    result.add(nums[i]);
                }
            }
            
            return result;
        }
    }
    
    
    

  • 0
    A

    good answer! It does help me!


  • 0
    A

    I guess you need another} that would make the code better~


  • 0
    M

    @aiboli Thanks, I corrected that.


Log in to reply
 

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