Flattening of arrays

1. What is array flattening

Array flattening refers to converting an array with multiple layers of nesting into an array without nesting. For example: [1, 2, 3], [4, [5, [6]]]] 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 the code

2. Realization of array flattening

1. Initial implementation

Flatten the array passed in and return it

(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 is an array, flatten it
        val.flatten(res)
      } else { // If it is not an array, just put the element in the res
        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 the code

2. Further implementation

It is easy to see that the initial implementation lacked the depth argument (the depth of anti-nesting) compared to flat in JS, which is added 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 is an array and 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 the code

Although the res parameter is more similar to the flat function after it is removed, in order to prevent the creation of an RES array every time the flatten function is executed, the recursive return value needs to be expanded once every time it is received, which wastes both time and space. Therefore, the RES parameter is not removed. As follows:

(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 the code

3. Final implementation

When flatten is called to depth === 1, it can be directly added to the RES array using the extension operator to improve program efficiency

Otherwise, not only would you have to recurse one more level, but you would have to go through multiple judgments each time you went through an element

(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 the code

3. Other implementation directions for array flattening

1. The use ofArray.prototype.reduceimplementation

(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 the code

2. The use ofArray.prototype.someimplementation

(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 the code

3. The use ofArray.prototype.spliceimplementation

(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 the code

4. The use ofstackimplementation

(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 the code