假设我有这样一个数组:
$array = array(
'word1',
'abc',
'abc',
'word2',
[other words]
'word1',
'dfg'
'word2',
[other words]
);
我需要找到两个给定单词之间的最小距离。(让'word1'和'word2'是这两个单词)
在这种情况下，word1和word2之间的最小距离是1，因为在第二组单词中，它们之间只有'dfg'分隔。
我写了一个简单的代码，但它太昂贵，我正在寻找一个更快的版本。
//> PSEUDO CODE
function minDistance( $words, $word1, $word2 ) {
foreach( $words as $k=>$v)
if ( $v == $words1 )
$positionsOfFirstWord[] = $k;
if ( $v == $words2 )
$positionsOfSecondWord[] = $k;
//> If word1 or word2 was not found in the array then
//> return max distance possibile (count($words))
//> Now we have 2 array containg the position of both word we need.
foreach( $positionsOfFirstWord as $v )
foreach( $positionsOfSecondWord as $vv )
$distance = abs($vv-$v);
}
注意$array中单词的顺序并不重要(这就是为什么有abs())
你觉得会有更好的版本吗?
请注意在这种情况下函数也必须返回1:
array(
[other words]
'word2',
'dfg',
'word1'
[other words]
);
我认为一个简单的循环就足够了。跟踪当前最小值和last word1，如果发现word2，则更新当前最小值。基本上你是在利用这样一个事实，即word2总是最接近最后一个找到的word1
let minimum = INFINITY
let lastword1 = -1
let lastword2 = -1
foreach word w in words
{
if ( w is word1 )
{
lastword1 = current position;
find distance between lastword2 and w update minimum if needed
}
if ( w is word2 )
{
lastword2 = current position;
find distance between lastword1 and w update minimum if needed
}
}
你可以在O(n)中做到这一点，但如果可以进行预处理，并且你需要回答多个查询，可能有更快的方法
构造一个int型数组，如下所示
- 从上到下遍历单词数组
- 如果遇到'word1'并且最后遇到的单词不是'word1'，则将该位置附加到正在构建的数组中
- 如果遇到'word2'并且最后遇到的单词不是'word2'，则将该位置附加到正在构建的数组中
- 如果遇到'word2'并且最后遇到的单词是'word2'，则将数组的最后一个元素更新到当前位置
现在扫描数组找出任意两对之间的最小差
除步骤4外，再重复此过程一次。用'word1'代替'word2'
你的答案是两个最小值中较小的
基于parapura我写了这个，不知道为什么，但它似乎工作得更慢
function minDistance2($words,$key1,$key2) {
if ($key1 == $key2)
return 0;
$min = false;
$p1 = false;
$p2 = false;
foreach($words as $k=>$v) {
$calc = false;
if ($v == $key1) {
$p1 = $k;
$calc = true;
} else if ($v == $key2) {
$p2 = $k;
$calc = true;
}
if ($calc) {
if ($p1===false || $p2===false)
continue;
$d = abs($p1-$p2) - 1;
if ($min === false || $d<$min )
$min = $d;
}
if ($min!==false && $min<=0)
return 0;
}
return ($min===false ? 0 : $min);
}
为什么要为位置设置一个数组?为什么不把它们保存为值，然后求差的绝对值呢?
function distance($words, $first, $second) {
$result = new Array();
for(i=0; i<words.length; i++) {
if($words[i] == $first) {
$firstPos = i;
} elseif($words[i] == $second) {
$secondPos = i;
$result[] = (abs($firstPos - $secondPos));
}
}
// Find the smallest number in the result array
$min = $result[0];
for(i=0; i<result.length; i++) {
if(result[i] < $min) {
$min = result[i];
}
}
return $min;
}