非法集资罪提供网站建设,东莞优化公司收费,wordpress实现微信支付,建设母婴网站的目的1. 题目
稀疏数组搜索。有个排好序的字符串数组#xff0c;其中散布着一些空字符串#xff0c;编写一种方法#xff0c;找出给定字符串的位置。
示例1:输入: words [at, , , , ball, , 其中散布着一些空字符串编写一种方法找出给定字符串的位置。
示例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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
将非空字符串和其序号存起来二分查找字符串返回其序号
class Solution {
public:int findString(vectorstring words, string s) {vectorpairstring,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 mid1;elsereturn w_id[mid].second;}return -1;}
};上面画蛇添足了直接遍历过一遍了还二分查找。。直接二分查找如下需要对空字符串进行处理跳过mid 也是挪至非空处
class Solution {
public:int findString(vectorstring 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 mid1;elsereturn mid;}return -1;}
};
