18.5 有個內含單詞的超大文本文件，給定任意兩個單詞，找出在這個文件中這兩個單詞的最短距離（也即相隔幾個單詞）。有辦法在O（1）時間里完成搜索操作嗎？解法的空間復雜度如何？

解法1：我們假設單詞word1和word2誰在前誰在后無關緊要。要解決此題，我們需要遍歷一次這個文件。在遍歷期間，我們會記下最后看見word1和word2的地方，并把它們的位置存入lastPosWord1和lastPosWord2中。碰到word1時，就拿他跟lastPosWord2比較，如有必要則更新min，然后更新lastPosWord1.每碰到word2時，我們也執行同樣的操作。遍歷結束后，就可以得到最短距離。

實現算法：

int ShortestDist(string text[], int n, string word1, string word2){int min = kMaxInt / 2;int pos1 = -min;int pos2 = -min;for(int pos=0; pos<n; ++pos){if(text[pos] == word1){pos1 = pos;int dist = pos1 - pos2;if(dist < min)min = dist;}else if(text[pos] == word2){pos2 = pos;int dist = pos2 - pos1;if(dist < min)min = dist;}}return min; }

如果上述代碼要重復調用（查詢其他單詞對的最短距離），可以構造一個散列表，記錄每個單詞及其出現的位置。然后，我們只需找到listA和listB中（算術）差值最小的那兩個值。

hash_map<string,vector<int> > listA;

hash_map<string,vector<int> > listB;

listA:{1,2,9,15,25}

listB:{4,10,19}

?

總結

以上是生活随笔為你收集整理的careercup-高等难度 18.5的全部內容，希望文章能夠幫你解決所遇到的問題。

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