我在寻找一个最聪明的解决方案。
我有一个包含不同位置的数组，它有起始点和结束点。
我想对数组进行排序，使"Start/From"点始终从前一个" to/End"点开始。
例如: Array
(
[0] => planner'boarding'BoardingPasses Object
(
[from] => Gerona Airport
[to] => Stockholm
)
[1] => planner'boarding'BoardingPasses Object
(
[from] => Madrid
[to] => Barcelona
)
[2] => planner'boarding'BoardingPasses Object
(
[from] => Stockholm
[to] => New York JFK
)
[3] => planner'boarding'BoardingPasses Object
(
[from] => Barcelona
[to] => Gerona Airport
)
)
对数组进行排序后，结果如下所示:
Array
(
[0] => planner'boarding'BoardingPasses Object
(
[from] => Madrid
[to] => Barcelona
)
[1] => planner'boarding'BoardingPasses Object
(
[from] => Barcelona
[to] => Gerona Airport
)
[2] => planner'boarding'BoardingPasses Object
(
[from] => Gerona Airport
[to] => Stockholm
)
[3] => planner'boarding'BoardingPasses Object
(
[from] => Stockholm
[to] => New York JFK
)
)
请看看我的算法，这是完美的工作，但我正在寻找更快速的解决方案，而不是使用foreach循环内部for/而不是使用array_map来获得起点。
<?php
class SortPlan implements SortInterface
{
public static $cards;
public static $ArrangedArray = [];
public static $items = [];
public static function ArrangePlan($cards)
{
// TODO: Implement SortPlan() method.
self::$items = $cards;
$from = array_map(function($e) { return $e->from; }, self::$items);
$to = array_map(function($e) {return $e->to;}, self::$items);
$getDiff = array_diff($from,$to);
array_push(self::$ArrangedArray,$cards[key($getDiff)]);
unset(self::$items[key($getDiff)]);
for($i = 0; $i < count(self::$items); $i++)
{
foreach (self::$items as $p) {
$des = end(self::$ArrangedArray);
if ($des->to == $p->from) {
array_push(self::$ArrangedArray, $p);
unset($cards[key($p)]);
}
}
}
print_r(self::$ArrangedArray);
return self::$ArrangedArray;
}
}
?>
我不懂php，所以我将提供一个通用算法。我的算法的时间复杂度为O(nlogn)。
首先将所有命名为frmarray的对象按from属性排序，创建一个不同的数组
然后将所有命名为toarray的对象按to属性排序，重新生成一个数组
到目前为止，排序时间为O(nlogn)
现在找到对象Obj这样的Obj.To != any object's From，这可以通过一次考虑一个对象，然后在数组frmarray
由于二进制查找需要O(log n)时间，并且我们对每个元素都进行查找，因此时间仍然为O(nlogn)。
对象Obj将是排序数组的最后一个元素。
在数组toarray上使用二进制查找可以很容易地找到second last元素，我们将搜索To = Obj.From .
同样，third last元素可以通过应用二进制搜索找到。
这一步也是O(nlogn)。因此我的算法的总时间复杂度为O(nlogn)
需求:对包含路线信息的登机牌列表进行排序，使相邻路线的"to"answers"from"相同。即目的地的有序列表。
示范:https://eval.in/662878
我使用的方法是:
- 创建匹配规则 的部分路由列表
- 每次有机会时合并部分列表。
:
- 由'from'键值的路由列表
- 由'to'键值的路由列表
- 快速访问路由当前所在的"部分列表"。
对于每条路由:
- 将其添加到from/to查找列表
- 将其添加到相应的"部分列表"
这就是有趣的地方:
我们检查相邻的路由是否已经在列表中。有多种可能性:注意:Adjacent Routes非常重要，使排序"不像我们想的那么快"。
问题是，没有明显的方法通过比较路由来决定哪个是"在"或"在"另一个之前或之后。我们可以比较的是它们是否彼此"直接相邻"。即。其中一个的"From"与另一个的"To"相匹配。或者反过来。
所以，我们的想法是建立"部分路径"，并在我们可以这样做的时候合并它们。
1)没有匹配-开始一个新的'部分路径'。
2)'From'或'To'匹配-添加到适当的列表中。
3)'From'和'to'都匹配。这意味着我们可以将两个"部分列表"连接在一起!
在所有合并结束时，将有一个路径(RoutePath)，所有的路由将指向。
代码:
BuildPath
类处理单个路由并决定处理哪个RoutePath:
class BuildPath {
/**
*
* Generate partially sorted lists of boarding passes
* when adding one at a time to an output list.
*
* Method:
* o Each route will get appended to the approriate partial list as it processed.
*
* o When the route will join two partial lists then that are merged
*
* Needed:
* o Fast lookup of adjacent routes to find out which list to appended to.
*
* o Fast lookup of the partial list
*/
/**
* Initial source array of boarding passes that hold routes
*
* @var array
*/
private $boardingPasses = null;
/**
* stdClass Route object indexed by 'From' keys
*
* @var array
*/
private $keyFrom = array();
/**
* stdClass Route object indexed by 'To' keys
*
* @var array
*/
private $keyTo = array();
/**
* @return void
*/
public function __construct(array $boardingPasses)
{
$this->boardingPasses = $boardingPasses;
foreach ($boardingPasses as $key => $pass) {
$route = current($pass);
$route->passId = $key; // so I can get as the full data later
$this->addRoute($route);
}
}
public function addRoute($route)
{
/*
* Can new route be joined to an existing route?
*/
// Will this route join two partial lists
if ( $this->canAddFrom($route->from)
&& $this->canAddTo($route->to) ) { // join two partial lists together
$this->keyFrom[$route->from] = $route;
$this->keyTo[$route->to] = $route;
// add to one list first - it doesn't matter which
$this->getAddFromPath($route->from)->add($route);
// merge the two partial paths together
$this->getAddFromPath($route->from)->merge($this->getAddToPath($route->to));
} elseif ($this->canAddFrom($route->from)) { // add to this ;ist
$this->keyFrom[$route->from] = $route;
$this->keyTo[$route->to] = $route;
$this->getAddFromPath($route->from)->add($route);
} elseif ($this->canAddTo($route->to)) { // add to existing path
$this->keyFrom[$route->from] = $route;
$this->keyTo[$route->to] = $route;
$this->getAddToPath($route->to)->add($route);
} else { // start a new path
$this->keyFrom[$route->from] = $route;
$this->keyTo[$route->to] = $route;
$path = new 'RoutePath();
$route->path = $path; // the path may change later
$path->add($route);
// $this->routes[] = $route;
return $route;
}
}
/**
* The original array in path order
*
* @return array
*/
public function getSortedRoutes()
{
$out = array();
foreach($this->getPath()->getRoutes() as $route) {
unset($route->path);
$out[] = $this->boardingPasses[$route->passId];
}
return $out;
}
/*
* All routes should point to the same path
*
* Whatever happens: each route will point to the path it is in :)
*
* So, a scan of all the routes for different paths will find all the partial paths :)
*/
public function getPath()
{
reset($this->keyFrom);
return current($this->keyFrom)->path;
}
// helpers
public function canAddFrom($from)
{
return isset($this->keyTo[$from]);
}
public function canAddTo($to)
{
return isset($this->keyFrom[$to]);
}
public function getAddFromPath($from)
{
return $this->keyTo[$from]->path;
}
public function getAddToPath($to)
{
return $this->keyFrom[$to]->path;
}
}
RoutePath
The class that holds the 'partial list' of adjacent routes:
class RoutePath {
private $path = array();
/**
* Add the route to the appropriate end of the list
*
* @param stdClass $route
*
* @return void
*/
public function add($route)
{
$route->path = $this; // ensure it pounts to correct path
if (empty($this->path)) {
array_push($this->path, $route);
} elseif ($this->canAddFrom($route->from)) {
array_push($this->path, $route);
} elseif ($this->canAddTo($route->to)) {
array_unshift($this->path, $route);
} else {
throw new 'Exception('Cannot add node: From: '. $route->from . ', To: '. $route->to, 500);
}
}
/**
* Merge two partial lists together
*
* o Decide which list to append to
*
* o Update all the routes to point to rthe merged path
*
* @param RoutePath $path
*
* @return void
*/
public function merge('RoutePath $path)
{
if ($this->canAddFrom($path->getFrom())) {
$path->updateRoutePath($this);
$this->path = array_merge($this->path, $path->getpath());
} elseif ($this->canAddTo($path->getTo())) {
$path->merge($this);
} else {
throw new 'Exception('Cannot merge paths: '
. ' (this): From: '. $this->getFrom() .', To: '. $this->getTo()
. ' (path): From: '. $path->getFrom() .', To: '. $path->getTo()
, 500);
}
}
/**
* Make all the routes point to the correct list
*
* @param RoutePath $path
*
* @return void
*/
public function updateRoutePath('RoutePath $path)
{
foreach ($this->path as $route) {
$route->path = $path;
}
}
// always check the first entry in the list
public function canAddTo($to)
{
return $this->getFrom() === $to;
}
// alway check last entry in the list
public function canAddFrom($from)
{
return $this->getTo() === $from;
}
public function getFrom()
{
reset($this->path);
return current($this->path)->from;
}
public function getTo()
{
return end($this->path)->to;
}
public function getpath()
{
return $this->path;
}
public function getRoutes()
{
return $this->path;
}
}
运行并显示输出:
$path = new BuildPath($passes);
// print output...
echo '<pre>Sorted...', PHP_EOL;
print_r($path->getSortedRoutes());
echo '</pre>';
输出示例:
Sorted...
Array
(
[0] => Array
(
[planner'boarding'BoardingPasses] => stdClass Object
(
[from] => Madrid
[to] => Barcelona
[passId] => 1
)
)
[1] => Array
(
[planner'boarding'BoardingPasses] => stdClass Object
(
[from] => Barcelona
[to] => Gerona Airport
[passId] => 3
)
)
[2] => Array
(
[planner'boarding'BoardingPasses] => stdClass Object
(
[from] => Gerona Airport
[to] => Stockholm
[passId] => 0
)
)
[3] => Array
(
[planner'boarding'BoardingPasses] => stdClass Object
(
[from] => Stockholm
[to] => New York JFK
[passId] => 2
)
)
)
$passes = Array(
0 => array('planner'boarding'BoardingPasses' =>
(object) array('from' => 'Gerona Airport', 'to' => 'Stockholm')
),
1 => array('planner'boarding'BoardingPasses' =>
(object) array('from' => 'Madrid', 'to' => 'Barcelona')
),
2 => array('planner'boarding'BoardingPasses' =>
(object) array('from' => 'Stockholm', 'to' => 'New York JFK')
),
3 => array('planner'boarding'BoardingPasses' =>
(object) array('from' => 'Barcelona', 'to' => 'Gerona Airport')
),
);