drgd73844 2011-12-19 00:36

# 更快地找到数组中单词之间的最小距离

Consider I have this array:

``````\$array = array(

'word1',
'abc',
'abc',
'word2',
[other words]
'word1',
'dfg'
'word2',
[other words]
);
``````

I need to find the minimum distance between 2 given words. (let 'word1' and 'word2' be these 2 words)

In this case the minium distance between `word1` and `word2` is 1 because in the second group of words they are separated by only 'dfg'.

I wrote a simple code but it's too expsensive and I am looking for a faster version.

``````//> 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);

}
``````

Note the order of words in \$array isn't important (that's why there is abs())

Do you think there could be a better version?

Please note the function must return 1 in this case too:

``````array(
[other words]
'word2',
'dfg',
'word1'
[other words]
);
``````
• 写回答

#### 4条回答默认 最新

• dqe9657 2011-12-19 00:41
关注

I think a simple loop is enough. Keep track over the current minimum and of the `last word1` and update current minimum if a `word2` is found. Basically you are utilizing the fact that a `word2` will always be closest to the last `word1` found

`````` 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
}

}
``````

You can do this in `O(n)` but there might faster ways if pre processing can be done and you need to answer multiple queries

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥15 Python如何爬取post请求头的数据