How to Realize Array Flattening (Flattening) Method in JavaScript Interview
- 2021-12-04 17:51:37
- OfStack
3.2 How to Determine If an Element Is an Array
3.3 Recursion
3.4 Initial implementation of the flat method
4 Optimization 4.1 Specifying Expansion Depth
4.2 Array Space Handling
4.2. 1 for... of increase vacancy judgment
4.2. 2 forEach, map method traversal
4.2. 3 reduce method
5 Others 5.1 Stack
5.2 Improvement
Summarize
1 What is array flat?
The concept is simple, meaning to reduce the dimension of a "multidimensional" array, such as:
// The original array is 1 A " 3 Dimension array
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
// Can be reduced to 2 Dimension
newArray1 = [1, 2, 3, 4, [5, 6], 7, 8, 9]
// It can also be reduced to 1 Dimension
newArray2 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Array flattening is also called array flattening and array dimensionality reduction.
Array Flapping Method in 2 JS Standard Library
The array flattening method Array. prototype. flat () has been implemented in the JavaScript standard library
The flat () method recursively iterates through the array at a specifiable depth and returns a new array by combining all the elements with the elements in the subarray that it iterates through.
Syntax: var newArray = arr. flat ([depth])
Parameter: depth is an optional value indicating the depth of the multidimensional array to be traversed, and the default value is 1. It can be understood as the number of layers you want to expand (or reduce the dimension).
Return value: A new array composed of the traversed elements and the elements of the subarray
Examples:
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
const newArray1 = array.flat() // Equivalent to array.flat(1) ; Drop 1 Dimension
// newArray1: [1, 2, 3, 4, [ 5, 6 ], 7, 8, 9]
const newArray2 = array.flat(2) // Drop 2 Dimension
// newArray2 : [1, 2, 3, 4, 5, 6, 7, 8, 9]
Special:
depth < When = 0, the returned array and the original array have 1 dimension (note that only the dimension is 1, see point 3 for vacancies)
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
array.flat(-1)
// [1, 2, [3, 4, [5, 6], 7], 8, 9]
depth=Infinity, the returned array becomes 1-dimensional
array.flat(Infinity)
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
There are vacancies in the original array, and the flat method eliminates the vacancies, even flat (0) eliminates the vacancies, so the first point says "only dimension 1". And the vacancy will be eliminated to which layer the flat method is expanded, and the vacancy in the deeper layer will not be eliminated
const array1 = [1, , 2, [3, ,4, [5, 6], 7], 8, 9]
// Notice that this array has two spaces
array.flat(0)
// [ 1, 2, [ 3, , 4, [ 5, 6 ], 7 ], 8, 9 ]
// No. 1 1 There are no vacancies, number one 2 There are still vacancies
3 Implement an flat method
flat method to expand 1 layer (1 dimension) steps: traverse the array, determine whether the current element is an array, if not an array, directly save; If it is an array, expand it and save it
The flat method expands multiple layers (reducing multiple dimensions) is nothing more than using recursion to perform the same operation on array sub-elements on the basis of expanding one layer.
You can split this method into three steps:
1. How to traverse an array
2. How to determine whether an element is an array
3. Recursion
To implement the above three steps, you can combine them to get different flat implementations
3.1 How to traverse an array
There are many methods, and three categories are introduced here:
1. for correlation
for cycle for...offor... in is built to traverse object properties and is not recommended for use with Array 1
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
// for Cycle
for (let i = 0; i < array.length; i++) {
const element = array[i];
}
// for...of
for (const element of array) {
}
2. Array method: A method that can directly get array elements
forEach() reduce() map()
// forEach()
array.forEach(element => {
});
// reduce()
array.reduce((pre, cur) => {
const element = cur
}, [])
// map()
array.map(element => {
})
3. Array method: The method that returns the traverser (Iterator) object
keys() values() entries()
// This 3 This way is just to get the traverser object, and it needs to be matched with for...of To traverse
// keys()
for (let i of array.keys()) {
const element = array[i]
}
// values()
for (let element of array.values() ) {
}
// entries()
for (let [i, element] of array.entries()) {
console.log(array[i])
console.log(element)
}
3.2 How to Determine If an Element Is an Array
There is a 1 variable a to judge whether it is an array. Here are four methods:
Array has a static method Array. isArray () for determining whether a variable is an array The instanceof operator is used to detect whether the constructor's prototype attribute appears on the prototype chain of an instance object.If a is an array, Array. prototype appears on its prototype chain Judging by the constructor of the object (this method may fail because constructor can be changed manually) Judging by Object. prototype. toString (), the method can return a string representing the object
// Method 1
Array.isArray(a)
// Method 2
a instanceof Array
// Method 3
a.constructor === Array
// Method 4
// Use call To call Object.prototype Above toString Method
Object.prototype.toString.call(a) === '[object Array]'
// You can't judge it that way, because this toString Has been covered Object.prototype.toString
// Only Object.prototype.toString Can correctly judge the type
a.toString()
3.3 Recursion
Recursion: Do the same for child elements
function flat() {
let res = []
Traversing an array {
if ( The current element is an array ) {
flat( Current element ) Get 1 Dimensional array
Will 1 Dimensional array spliced to res Medium
} else {
res.push( Current element )
}
}
return res
}
3.4 Preliminary implementation of flat method
Choose the traversal mode and the way to judge the array, and match recursion to initially realize flat method, such as:
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
const newArray1 = array.flat() // Equivalent to array.flat(1) ; Drop 1 Dimension
// newArray1: [1, 2, 3, 4, [ 5, 6 ], 7, 8, 9]
const newArray2 = array.flat(2) // Drop 2 Dimension
// newArray2 : [1, 2, 3, 4, 5, 6, 7, 8, 9]
The myFlat method can flatten a "multidimensional" array to a 1-dimensional array, but it cannot specify an expansion depth depth and cannot handle array vacancies
4 Optimization
4.1 Specifying Expansion Depth
Dealing with unfolding depth is actually very simple. We can add a recursive termination condition, that is, depth < = 0 with the following code:
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
const newArray1 = array.flat() // Equivalent to array.flat(1) ; Drop 1 Dimension
// newArray1: [1, 2, 3, 4, [ 5, 6 ], 7, 8, 9]
const newArray2 = array.flat(2) // Drop 2 Dimension
// newArray2 : [1, 2, 3, 4, 5, 6, 7, 8, 9]
4.2 Array Space Handling
In fact, we should try to avoid empty arrays
We mentioned earlier that different methods of traversing arrays deal with array vacancies differently
Among them, the vacancies encountered in forEach, reduce and map will be directly ignored; While for... of does not ignore it, it will treat it as undefined when it encounters vacancies
4.2. 1 for... of increase vacancy judgment
So we need to improve for... of's myFlat method of traversing an array:
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
const newArray1 = array.flat() // Equivalent to array.flat(1) ; Drop 1 Dimension
// newArray1: [1, 2, 3, 4, [ 5, 6 ], 7, 8, 9]
const newArray2 = array.flat(2) // Drop 2 Dimension
// newArray2 : [1, 2, 3, 4, 5, 6, 7, 8, 9]
4.2. 2 forEach, map method traversal
Of course, you can also use forEach, map methods to traverse the array, so you don't have to judge manually
But there is a special case to consider, that is, when depth < When = 0, we use the filter method to eliminate array vacancies
// forEach
function myFlat(arr, depth = 1) {
if (depth <= 0) {
return arr.filter(item => item !== undefined);
}
let res = [];
arr.forEach((item) => {
if (Array.isArray(item)) {
res = res.concat(myFlat(item, depth - 1));
} else {
res.push(item);
}
});
return res;
}
// map
function myFlat(arr, depth = 1) {
if (depth <= 0) {
return arr.filter(item => item !== undefined);
}
let res = [];
arr.map((item) => {
if (Array.isArray(item)) {
res = res.concat(myFlat(item, depth - 1));
} else {
res.push(item);
}
});
return res;
}
4.2. 3 reduce method
Among them, reduce method is the most concise, and it is also one of the methods that are often tested in interviews
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
const newArray1 = array.flat() // Equivalent to array.flat(1) ; Drop 1 Dimension
// newArray1: [1, 2, 3, 4, [ 5, 6 ], 7, 8, 9]
const newArray2 = array.flat(2) // Drop 2 Dimension
// newArray2 : [1, 2, 3, 4, 5, 6, 7, 8, 9]
5 Others
5.1 Stack
In theory, recursive methods can usually be converted into non-recursive methods, that is, using stack
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
const newArray1 = array.flat() // Equivalent to array.flat(1) ; Drop 1 Dimension
// newArray1: [1, 2, 3, 4, [ 5, 6 ], 7, 8, 9]
const newArray2 = array.flat(2) // Drop 2 Dimension
// newArray2 : [1, 2, 3, 4, 5, 6, 7, 8, 9]
However, this method cannot specify the expansion depth, and can only be completely expanded into a 1-dimensional array
5.2 Improvement
To improve the disadvantage that the stack cannot specify the expansion depth, the code is as follows:
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
const newArray1 = array.flat() // Equivalent to array.flat(1) ; Drop 1 Dimension
// newArray1: [1, 2, 3, 4, [ 5, 6 ], 7, 8, 9]
const newArray2 = array.flat(2) // Drop 2 Dimension
// newArray2 : [1, 2, 3, 4, 5, 6, 7, 8, 9]