基于divide函数，如何通过扁平化数组索引获取树形数组节点路径？

To solve the problem of mapping a flat array index to its path in the nested tree created by your divide function, we can break down the logic into calculating hierarchical block sizes and using integer division to find each level's index.

Core Concept #

Your divide function builds a tree where each level splits the array into chunks of size size, repeating until the top-level array has ≤ size elements. Each level corresponds to grouping elements into larger blocks as we move up the tree. For example, with size=5 and 100 elements:

• The deepest level uses blocks of 1 element (individual values).
• The middle level uses blocks of 5 elements (first-round chunks).
• The top level uses blocks of 25 elements (groups of 5 middle-level chunks).

To find the path, we calculate how many times we need to split the array to reach the final tree structure, then work backwards from the flat index to find each level's position.

General Algorithm #

1. Validate the input: Ensure the flat index is within bounds of the original array.
2. Calculate split depth: Determine how many recursive splits are needed to get a top-level array with ≤ size elements.
3. Compute the path: For each level (from top to bottom), use integer division to find the index in that level, then update the remaining index using the remainder.

Implementation Code #

function getPathToIndex(flatIndex, chunkSize, originalArrayLength) {
    // Check if the index is valid
    if (flatIndex < 0 || flatIndex >= originalArrayLength) {
        throw new Error("Index is out of the original array's bounds");
    }

    let currentChunkCount = Math.ceil(originalArrayLength / chunkSize);
    let splits = 0;

    // Figure out how many recursive splits are required
    while (currentChunkCount > chunkSize) {
        currentChunkCount = Math.ceil(currentChunkCount / chunkSize);
        splits++;
    }

    const path = [];
    let remainingIndex = flatIndex;

    // Calculate each level's index starting from the top of the tree
    for (let exponent = splits + 1; exponent >= 0; exponent--) {
        const blockSize = Math.pow(chunkSize, exponent);
        const levelIndex = Math.floor(remainingIndex / blockSize);
        path.push(levelIndex);
        remainingIndex = remainingIndex % blockSize;
    }

    return path;
}

// Example matching your scenario
const originalDataLength = 100;
const chunkSize = 5;
const targetIndex = 41; // 42nd element with value 2

const path = getPathToIndex(targetIndex, chunkSize, originalDataLength);
console.log(path); // Output: [1, 3, 1]

Example Breakdown #

For targetIndex=41, chunkSize=5, and originalDataLength=100:

1. We find we need 1 recursive split (100 →20 chunks, then 20→4 chunks which is ≤5).
2. Block sizes are 25 (5²), 5 (5¹), and 1 (5⁰).
3. • 41 //25 =1 (top-level index), remainder 16.
   • 16//5=3 (middle-level index), remainder 1.
   • 1//1=1 (deepest-level index).
4. The path [1,3,1] correctly points to the element at flat index 41 in the nested tree.

Edge Case Handling #

• Small arrays: If the original array length ≤ chunkSize, the path will have two elements (e.g., index 0 in a 3-element array with chunkSize=5 gives [0,0]).
• Non-divisible lengths: Even if the array length isn't a multiple of chunkSize, integer division and remainders still accurately map the index (e.g., index 6 in a 7-element array with chunkSize=3 gives [2,0]).

内容的提问来源于stack exchange，提问作者Lance Pollard