drgd73844 2011-12-19 00:36
浏览 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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(3条)

报告相同问题?