1. 題目

有個內含單詞的超大文本文件，給定任意兩個單詞，找出在這個文件中這兩個單詞的最短距離(相隔單詞數)。
如果尋找過程在這個文件中會重復多次，而每次尋找的單詞不同，你能對此優化嗎?

示例： 輸入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student" 輸出：1提示： words.length <= 100000

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/find-closest-lcci
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：

LeetCode 243. 最短單詞距離
LeetCode 244. 最短單詞距離 II（哈希map+set二分查找）
LeetCode 245. 最短單詞距離 III

• 如果多次查詢，建立multimap，查找 $\log n$ 復雜度
• 用multimap（底層是紅黑樹，平衡二叉搜索樹）
• key 是單詞，value 是 序號
• 該結構有序

class Solution {multimap<string,int> m; public:int findClosest(vector<string>& words, string word1, string word2) {for(int i = 0; i < words.size(); ++i)m.insert(make_pair(words[i],i));auto it1 = m.lower_bound(word1), end1 = m.upper_bound(word1);auto it2 = m.lower_bound(word2), end2 = m.upper_bound(word2);int dis = INT_MAX;while(it1 != end1 || it2 != end2){while(it1 != end1 && it2 != end2 && it1->second < it2->second)dis = min(dis, it2->second - it1++->second);while(it1 != end1 && it2 != end2 && it2->second < it1->second)dis = min(dis, it1->second - it2++->second);if(it1 == end1 && it2 != end2){it1--;while(it2 != end2){dis = min(dis, abs(it1->second - it2++->second));}it1++;}else if(it1 != end1 && it2 == end2){it2--;while(it1 != end1){dis = min(dis, abs(it2->second - it1++->second));}it2++;}}return dis;} };

總結

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 17.11. 单词距离（multimap平衡二叉搜索树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。