0

拆分这些相对链接的最佳解决方案是什么

folder-1/folder-2/item-a.txt
folder-1/folder-2/item-b.txt
folder-1/folder-3/item-c.txt
folder-1/folder-3/item-a.txt
folder-1/item-f.txt
folder-1/folder-2
folder-1/folder-3
folder-1
item-b.txt
item-g.txt

进入php数组?

$testArray = array(
    "folder-1/" => array(
        "folder-2" => array(
            "item-a.txt",
            "item-b.txt"
        ),
        "folder-3" => array(
            "item-a.txt",
            "item-c.txt"
        ),
        "item-f.txt"
    ),
    "item-b.txt",
    "item-g.txt",
);
4

1 回答 1

2

给定d最深路径的深度和路径数,您可以在最坏情况 O (nk) 中非常简单地做到这一点,假设查找是恒定的(在 PHP 中就是这种情况):

$root = array();

foreach ($I as $i) {
    $d =& $root;
    $P = explode("/", $i);

    foreach ($P as $p) {
        if (!array_key_exists($p, $d))
            $d[$p] = array();

        $d =& $d[$p];
    }
}

您可以通过以确保父目录出现在任何子目录之前的方式对输入进行排序来预处理您的输入,从而进一步优化这一点。

然后您确定必须添加每个下一个条目(因此 -array_key_exists条件是多余的)。那么你只需要一个聪明的方法来知道将你的“光标”放在哪里$r。这段代码可能有点复杂。

此外,我不完全确定在哪一点预处理和导航的成本$r将有利于一般时间复杂度。

于 2014-06-16T00:19:31.150 回答