Java easy to understand solution, with example step by step analysis


  • 0
    P

    The main idea is to use the index and negative sign to indicate if a number exists, because index range [0, n - 1] can represents number range [1, n]

    class Solution {
    // [4, 3, 2, 7, 8, 2, 3, 1]
    // [4, 3, 2, -7, 8, 2, 3, 1]
    // [4, -3, -2, -7, 8, 2, 3, 1]
    // [4, -3, -2, -7, 8, 2, -3, 1]
    // [4, -3, -2, -7, 8, 2, -3, -1]
    // [4, -3, -2, -7, 8, 2, -3, -1] add 2
    // [4, -3, -2, -7, 8, 2, -3, -1] add 3
    // [-4, -3, -2, -7, 8, 2, -3, -1]
    public List<Integer> findDuplicates(int[] nums) {
    List<Integer> res = new ArrayList<Integer>();

        for(int i = 0; i < nums.length; i++) {
            int curNum = Math.abs(nums[i]);
            
            if(nums[curNum - 1] < 0) res.add(curNum);
            else nums[curNum - 1] = - nums[curNum - 1];
        }
        
        return res;
    }
    

    }


Log in to reply
 

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