1. 題目

稀疏數(shù)組搜索。有個(gè)排好序的字符串?dāng)?shù)組，其中散布著一些空字符串，編寫一種方法，找出給定字符串的位置。

示例1:輸入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"輸出：-1說明: 不存在返回-1。示例2:輸入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"輸出：4提示: words的長度在[1, 1000000]之間

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sparse-array-search-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 將非空字符串和其序號，存起來
• 二分查找字符串，返回其序號

class Solution { public:int findString(vector<string>& words, string s) {vector<pair<string,int>> w_id;for(int i = 0; i < words.size(); ++i)if(words[i] != "")w_id.push_back({words[i],i});int l = 0, r = w_id.size()-1, mid;while(l <= r){mid = l+((r-l)>>1);if(s < w_id[mid].first)r = mid-1;else if(s > w_id[mid].first)l = mid+1;elsereturn w_id[mid].second;}return -1;} };

• 上面畫蛇添足了，直接遍歷過一遍了，還二分查找。。
• 直接二分查找如下：需要對空字符串進(jìn)行處理跳過，mid 也是挪至非空處

class Solution { public:int findString(vector<string>& words, string s) {int l = 0, r = words.size()-1, mid;while(l <= r){while(l <= r && words[l]=="")l++;while(l <= r && words[r]=="")r--;mid = l+((r-l)>>1);while(l <= mid && words[mid]=="")mid--;// while(r >= mid && words[mid]=="") //這樣寫也行// mid++;if(s < words[mid])r = mid-1;else if(s > words[mid])l = mid+1;elsereturn mid;}return -1;} };

總結(jié)

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 10.05. 稀疏数组搜索（二分查找）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。