Почему неправильно считает глубину массива?

Question

Глубина массива в примере равна 2, а код выводит 3? Проблема в замыкании, поясните пожалуйста как это работает?

    let res = 1
function f(arr) {
    console.log(`arr - ${arr}`)
    arr.forEach(item => {
        if(Array.isArray(item)){
            ++res
            f(item,res)
        }
    })
}

f([1, 2, 3, [1], 4, 5, [1]])

Answer 1

Если несколько элементов текущего массива сами являются массивами, то не нужно наращивать счётчик глубины на каждом элементе-массиве. Нужно посчитать глубину для каждого элемента-массива и выбрать из них максимальную. Итоговая глубина для текущего массива — это максимальная среди глубин элементов-массивов + 1.

Как-то так:

function searchArrDepth(arr) {
    if (!Array.isArray(arr))
        return 0;

    let depth = 0;
    for (let item of arr)
        depth = Math.max(depth, searchArrDepth(item));
    return 1 + depth;
}

Или более компактно:

function searchArrDepth(arr) {
    if (!Array.isArray(arr))
        return 0;
    return 1 + arr.reduce((depth, item) => Math.max(depth, searchArrDepth(item)), 0);
}
    
console.log(searchArrDepth( [1, 2, 3, [1], 4, 5, [1]] ));
console.log(searchArrDepth( [] ));
console.log(searchArrDepth( [1, 2, 3] ));
console.log(searchArrDepth( [[1], [2], [3]] ));
console.log(searchArrDepth( [1, [2, [3, [4, [5, [6]]]]]] ));
console.log(searchArrDepth( {} ));
console.log(searchArrDepth( [[[[[]]]]] ));

Например, пусть есть массив вида (здесь [...] обозначает некоторый массив)

arr = [1, [...], 3, [...], 5];

У данного массива 5 элементов. Причём два из них — это элементы-массивы. Подсчитаем сколь глубоко здесь вложены массивы.

Во-первых, учитываем сам массив arr и полагаем, что глубина равна 1.

Теперь переберём элементы массива arr и для каждого элемента найдём его глубину. Если элемент не является массивом (!Array.isArray(arr[i]) === true), то считаем, что его глубина равна нулю. Получившийся массив глубин может быть, например, таким:

[0, 1, 0, 5, 0]

Среди всех найденных глубин выберем максимальную — 5.

Итоговая глубина есть максимальная среди всех глубин элементов массива arr (т.е. 5) + 1 (учли сам массив arr).

Заметим, что массив глубин [0, 1, 0, 5, 0] не обязательно формировать явно. Мы можем последовательно перебирать элементы массива arr, сравнивая их глубину с текущей максимальной глубиной, и при необходимости обновлять текущую максимальную глубину. Т.е. как-то так:

depth = 0;

depth = max(depth, searchArrDepth(arr[0])) = max(0, 0) = 0
depth = max(depth, searchArrDepth(arr[1])) = max(0, 1) = 1
depth = max(depth, searchArrDepth(arr[2])) = max(1, 0) = 1
depth = max(depth, searchArrDepth(arr[3])) = max(1, 5) = 5
depth = max(depth, searchArrDepth(arr[4])) = max(5, 0) = 5

Именно это и делает код

for (let item of arr)
    depth = Math.max(depth, searchArrDepth(item));

Здесь item последовательно принимает значения arr[0], arr[1], и т.д. Для каждого элемента массива мы находим его глубину searchArrDepth(item), и обновляем максимум depth = Math.max(depth, searchArrDepth(item)).

Наконец, возвращаем из функции максимум среди глубин элементов + 1 (сам массив arr): return 1 + depth;.

И самое главное, наш массив arr ничем принципиально не отличается от своих элементов-массивов. Также как для каждого элемента массива arr мы вызываем функцию searchArrDepth, так и для самого массива arr мы можем вызвать функцию searchArrDepth.

БЛОГ НА HUSL

Почему неправильно считает глубину массива?

Ответы (1 шт):