Javascript simple solution with explaination


  • 0
    C

    Let's say the array looks like this
    [4,3,2,7,8,2,3,1]

    We iterate over the entire array and try to put the correct numbers to the correct spots. If we find a duplicate we label the number by adding a minus sign to it.

    In each iteration we will make the number on location i a correct number or a duplicate number. At the end of the iteration the entire array would only have correct numbers or duplicate numbers.

    The iteration is as follows

    [ 4, 3, 2, 7, 8, 2, 3, 1, 9, 8 ] // original array
    [ 7, 3, 2, 4, 8, 2, 3, 1, 9, 8 ] // swap 4,7 in the last step
    [ 3, 3, 2, 4, 8, 2, 7, 1, 9, 8 ] // swap 4, 3
    [ 2, 3, 3, 4, 8, 2, 7, 1, 9, 8 ] // swap 3, 2
    [ 3, 2, 3, 4, 8, 2, 7, 1, 9, 8 ] // try to swap 3,3, so we have a duplicate here. Also this the end of the first iteration (i=0)
    
    [ -3, 2, 3, 4, 8, 2, 7, 1, 9, 8 ] // 2 is on the correct location
    [ -3, 2, 3, 4, 8, 2, 7, 1, 9, 8 ] // 3 is on the correct location
    [ -3, 2, 3, 4, 8, 2, 7, 1, 9, 8 ] // 4 is on the correct location
    [ -3, 2, 3, 4, 8, 2, 7, 1, 9, 8 ]
    [ -3, 2, 3, 4, 1, 2, 7, 8, 9, 8 ] // swap 8, 1
    [ 1, 2, 3, 4, -3, 2, 7, 8, 9, 8 ] // swap 1, -3
    [ 1, 2, 3, 4, -3, 2, 7, 8, 9, 8 ] // end of this iteration, and everything to the right is either a duplicate or on the correct location
    [ 1, 2, 3, 4, -3, -2, 7, 8, 9, 8 ] // 2 = 2, found another duplicate
    [ 1, 2, 3, 4, -3, -2, 7, 8, 9, 8 ] 
    [ 1, 2, 3, 4, -3, -2, 7, 8, 9, 8 ]
    [ 1, 2, 3, 4, -3, -2, 7, 8, 9, 8 ]
    [ 1, 2, 3, 4, -3, -2, 7, 8, 9, -8 ]
    

    The code is as follows:

    /**
     * @param {number[]} nums
     * @return {number[]}
     */
    var tmp
    var traverse = function(nums, i) {
      if (nums[i] < 0) {
        return // this is already a duplicate
      }
      if (i === nums[i] - 1) {
        return // this point is on the correct location
      }
      if (nums[i] === nums[nums[i] - 1]) {
        // if (nums[i] - 1 > i) {
          nums[i] = -nums[i]
        // } else {
          // nums[nums[i] - 1] = -nums[i]
        // }
      } else { // swap the two numbers, we used an O(1) space here
        tmp = nums[nums[i] - 1]
        nums[nums[i] - 1] = nums[i]
        nums[i] = tmp
        traverse(nums, i)
      }
    }
    
    var findDuplicates = function(nums) {
      if (!nums) return []
      if (!nums.length) return nums
    
      for (var i=0; i<nums.length; i++) {
        traverse(nums, i)
      }
      return nums.filter(function(a) {return a < 0}).map(function(d) {return -d})
    };
    

Log in to reply
 

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