给定其扁平数组索引，如何在数组树中找到节点的路径？

问题描述

这是：

const data = [
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
]

function divide(data, size) {
  const result = []

  for (let i = 0; i < data.length; i += size) {
    const chunk = data.slice(i, i + size);
    result.push(chunk)
  }

  if (result.length > size) {
    return divide(result, size)
  }

  return result;
}

const result = divide(data, 5);
console.log(result)

data 数组只是一个整数数组。但是，当通过 divide 运行它时，它会生成一棵嵌套的数组树，每个数组的最大 size 。我怎么说给我42号商品？在已编译树形版本中数组？例如，我想要这里的 2 值，即数字42（索引41），如果这是树的样子，则为：

The data array is simply an array of integers. However, when you run it through divide, it produces a tree of nested arrays with a maximum size of each array. How can I say "give me item number 42" in the tree version of the "compiled" array? For example, I want this 2 value right here, which is number 42 (index 41), if this is sorta what the tree looks like:

[                                                                                       ]
 [                   ],[                   ],[                   ],[                   ]
  [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]
   1   6   1   6   1     6   1   6   1   6     1   6   1   6   1     6   1   6   1   6
   2   7   2   7   2     7   2   7  (2)  7     2   7   2   7   2     7   2   7   2   7
   3   8   3   8   3     8   3   8   3   8     3   8   3   8   3     8   3   8   3   8
   4   9   4   9   4     9   4   9   4   9     4   9   4   9   4     9   4   9   4   9
   5   0   5   0   5     0   5   0   5   0     5   0   5   0   5     0   5   0   5   0

路径为 [0，1， 3，1] 。给定数组中的索引41，如何快速最佳地获取此路径？鉴于上面的 divide 函数以及将数组任意分块为不同大小的容器，一般方程是什么？

The path to it is [0, 1, 3, 1]. How can I quickly and most optimally get this path given the index 41 in the array? What is the general equation given the divide function above and arbitrary chunking of the array into different sized bins?

根据@Quade的回答，这是我迄今为止最好的方法。

This is as best as I can start so far, based on @Quade's answer:

let i = 42
let s = 5
let d = 3
let x = 0
let v = new Array(d)
while (d) {
  if (i < s ** d) {
    v[x] = 0
  } else {
    v[x] = Math.floor(i / (s ** d))
  }
  d--
  x++
}

推荐答案

基本上，路径是以基数 size 表示的索引，其中后者是除法的最大数组大小。例如，以5为底的41是131。因此[1，3，1]。我认为您错误地为此前缀加上了0（只需在代码段中尝试 console.log（result [1] [3] [1]））即可。

Essentially the path is the index expressed in base size, where the latter is the maximum array size of the division. For example, 41 in base 5 is 131. Hence [1, 3, 1]. I think you mistakenly prefixed this with an additional 0 (just try console.log(result[1][3][1]) in your snippet).

现在，对于较低的索引，您将需要预填充一个或多个零，以便给定树的路径长度始终相同。您需要的位数取决于树的深度，该深度由数据中的最大索引确定。在您的示例中，数据的大小为100，因此最大索引为99。以5为底的99仍为3位数字。因此，在这种情况下，任何路径都应包含3位数字。

Now, for lower indexes, you would need to prepad one or more zeroes so the path length is always the same for a given tree. The number of digits you need depends on the depth of the tree, which is determined by the largest index in the data. In your example, your data has a size of 100, so largest index is 99. 99 in base 5 is still 3 digits. So any path should have 3 digits in this case.

分隔函数当前无法产生正确的结果。在这种情况下，它应该只返回原始数组，但是您的代码仍将其包装在另一个数组中。

The divide function currently does not produce the correct result when the data size is smaller than the chunk size. In that case it should just return the original array, but your code still wraps it in another array.

解决方法是在开始时进行大小检查：

The fix is to make the size check at the start:

if (data.length <= size) return data;




实现

Implementation

// Get path. Note that the actual tree is not needed; just the data size and chunk size
function getPath(chunkSize, dataSize, index) {
    if (index >= dataSize) throw new Error("index out of range");
    // Take logarithm, base chunkSize, from the highest possible index (i.e. dataSize - 1)
    let depth = Math.floor(Math.log(dataSize - 1) / Math.log(chunkSize)) + 1;
    let path = [];
    for (let i = 0; i < depth; i++) {
        // get each "digit" of the index when represented in base-chunkSize
        path.push(index % chunkSize);
        index = Math.floor(index / chunkSize);
    }
    return path.reverse();
}

let path = getPath(5, 100, 41);
console.log("path", path);

// Create the tree and extract that number at that index:
const data = [
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
]

// I moved the base case detection first, so it works correctly
//   for trees that are just the original array.
function divide(data, size) {
    if (data.length <= size) return data;
    const result = [];
    for (let i = 0; i < data.length; i += size) {
        result.push(data.slice(i, i + size))
    }
    return divide(result, size);
}

const tree = divide(data, 5);

// Now get the value using the path we got
let drill = tree;
while (path.length) {
    drill = drill[path.shift()];
}
console.log("value at path", drill);

这篇关于给定其扁平数组索引，如何在数组树中找到节点的路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！