Flattening of arrays

1. What is array flattening

The so-called flattening of arrays , It refers to converting an array with multiple nested layers into an array without nesting . for example : take [1, [2, 3], [4, [5, [6]]]] Convert into [1, 2, 3, 4, 5, 6]

const arr = [1, [2, 3], [4, [5, [6]]]]
arr.flat(3) //=> [1, 2, 3, 4, 5, 6]
 Copy code 

2. Implementation of array flattening

1. Initially realized

Flatten the passed in array and return

(function() {
  function flatten(res = []) {
    const array = this
    
    for (let i = 0, len = array.length; i < len; i ++) {
      const val = array[i]
      
      if (Array.isArray(val)) { //  If it's an array ,  Flatten it 
        val.flatten(res)
      } else { //  If it's not an array ,  Then put the element directly into  res  that will do 
        res.push(val)
      }
    }
    
    return res
  }
  
  Array.prototype.flatten = flatten
})()

const array = [1, 2, [3, [4, [5, 6, [7, 8]]]]]
array.flatten() //=> [1, 2, 3, 4, 5, 6, 7, 8]
 Copy code 

2. Further realization

It's easy to see , and JS Medium flat comparison , The initial implementation was less depth Parameters ( Anti nesting depth ), Add here

(function() {
  function flatten(depth = 1, res = []) {
    const array = this
    
    for (let i = 0, len = array.length; i < len; i ++) {
      const val = array[i]
      
      if (Array.isArray(val) && depth > 0) {
        //  If  val  It's an array ,  And it needs to be flattened 
        val.flatten(depth - 1, res)
      } else {
        res.push(val)
      }
    }
    
    return res
  }
  
  Array.prototype.flatten = flatten
})()

const array = [1, 2, [3, [4, [5, 6, [7, 8]]]]]
array.flatten(3) //=> [1, 2, 3, 4, 5, 6, [7, 8]]
 Copy code 

Although remove res The parameter is closer to flat function , But to prevent every execution flatten Functions need to create a res Array , Each time you accept a recursive return value, you also need to expand it , It's a waste of time , It's a waste of space , So... Is not removed res Parameters . As shown below :

(function() {
  function flatten(depth = 1) {
    const array = this
    const res = []
    
    for (let i = 0, len = array.length; i < len; i ++) {
      const val = array[i]
      
      if (Array.isArray(val) && depth > 0) {
        res.push(...val.flatten(depth - 1))
      } else {
        res.push(val)
      }
    }
    
    return res
  }
  
  Array.prototype.flatten = flatten
})()
 Copy code 

3. Final realization

When flatten Call to depth === 1 when , Directly use the extension operator to add to res The array can be , Improve program efficiency

otherwise , You don't just need another layer of recursion , And every time you traverse an element, you have to go through multiple judgments

(function() {
  function flatten(depth = 1, res = []) {
    const array = this
    
    for (let i = 0, len = array.length; i < len; i ++) {
      const val = array[i]
      
      if (Array.isArray(val) && depth > 0) {
        if (depth === 1) {
          res.push(...val)
        } else {
          val.flatten(depth - 1, res)
        }
      } else {
        res.push(val)
      }
    }
    
    return res
  }
  
  Array.prototype.flatten = flatten
})()

const array = [1, 2, [3, [4, [5, 6, [7, 8]]]]]
array.flatten(3) //=> [1, 2, 3, 4, 5, 6, [7, 8]]
 Copy code 

3. Other implementation directions of array flattening

1. utilize Array.prototype.reduce Realization

(function() {
  function flatten() {
    const array = this
    const res = array.reduce((prevVal, curVal) => {
      return prevVal.concat(Array.isArray(curVal) ? curVal.flatten() : curVal)
    }, [])
    return res
  }
  
  Array.prototype.flatten = flatten
})()
 Copy code 

2. utilize Array.prototype.some Realization

(function() {
  function flatten() {
    const array = this
    const res = [...array]
    while (res.some(item => Array.isArray(item))) {
      res = [].concat(...res)
    }
    return res
  }
  
  Array.prototype.flatten = flatten
})()
 Copy code 

3. utilize Array.prototype.splice Realization

(function() {
  function flatten() {
    const array = this
    const res = [...array]
    
    for (let i = 0; i < res.length; i ++) {
      if (Array.isArray(res[i])) {
        res.splice(i, 1, ...res[i])
        i --
      }
    }
    
    return res
  }
  Array.prototype.flatten = flatten
})()
 Copy code 

4. utilize stack Realization

(function() {
  function flatten() {
    const array = this
    const stk = [...array]
    const res = []
    
    while (stk.length) {
      let topVal = stk.pop()
      if (Array.isArray(topVal)) {
        stk.push(...topVal)
      } else {
        res.push(topVal)
      }
    }
    
    return res.reverse()
  }
  Array.prototype.flatten = flatten
})()
 Copy code