稀疏矩阵搜索（两种方法解决：1.暴力+哈希 2.二分法）

题目：

有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。

示例：

 输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
 输出：-1
 说明: 不存在返回-1。
 输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
 输出：4

解题思路:

首先，简单的可以用暴力+哈希来实现。

创建哈希表，并建立每个字符串与其下标的映射关系；

然后找是否存在key值（字符串s），存在则返回哈希表中的value值；

否则说明不存在该字符串，返回-1。

Code：

class Solution {
public:int findString(vector<string>& words, string s) {unordered_map<string,int> map;//创建哈希表//建立每个单词与其下标的映射关系for(int i=0;i<words.size();i++){map[words[i]]=i;}//直接找字符串//找到了，直接返回value值if(map.find(s)!=map.end()){return map[s];}//没找到，返回-1return -1;}
};

 再升级一下，采用二分法来实现。

思路：

1.先将数组前后的空字符串清除

2.如果mid下标遇到空字符串，统一向右靠，当mid=right时，我们直接更新右边界到mid的位置

3.剩下接着按照常规的二分查找法进行目标字符串的查找

 Code：

class Solution {
public:int findString(vector<string>& words, string s) {int left = 0, right = words.size() - 1;while (left <= right) {//左边界遇到空字符串，左边界向右移if (words[left].size() == 0) {left++;continue;}//右边界遇到空字符串，右边界向左移if (words[right].size() == 0) {right--;continue;}//中间下标midint mid = (right + left) / 2;//如果遇到空字符串，统一向右靠while (words[mid].size() == 0) {mid++;//如果此时mid已经到达右边界，那么将右边界更新到中间下标mid处//这里right下标处的值会在后面判断到，不会被漏掉if (mid == right) {right = (right + left) / 2;continue;}}//这里顺便将刚刚上一步的右边界的值判断了，并没有漏掉//剩下的就是二分法常规查找if (words[mid] == s)return mid;else if (words[mid] > s) {right = mid - 1;}else {left = mid + 1;}}return -1;}
};