题目链接:面试题 10.05. 稀疏数组搜索 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:
稀疏数组搜索。有个排好序的字符串数组,其中散布着一些空字符串,编写一种方法,找出给定字符串的位置。
示例:
示例1: 输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta" 输出:-1 说明: 不存在返回-1。 示例2: 输入:words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball" 输出:4 提示: words的长度在[1, 1000000]之间
题目分析:
使用极其标准的二分查找模板,再加上搜索mid时的线性查找得
源码:
#include<bits/stdc++.h> #include<unordered_map> using namespace std; int main() { vector<string>words = { "CitZMIXZKoFbxvOlaza", "hBlKXdKJfBD" }; string s("hBlKXdKJfBD"); int l = 0, r = words.size() - 1, mid; while (l <= r) { mid = (l + r) >> 1; while (words[mid] == "" && mid < r)//线性查找符合要求的mid值 { mid++; } if (words[mid].compare(s) == 0) { r = mid; break; } if (mid == r ) { r = mid - 1; continue; } if (words[mid].compare(s) < 0) l = mid + 1; else r = mid - 1; } cout << (words[r].compare(s) == 0 ? r : -1); } /* vector<string>words = { "at", "", "", "", "ball", "", "", "car", "", "","dad", "", "" }; string s("ta"); -1 vector<string>words = { "E jgeVQIZI", "EMuBXhHEDpDOS", "HhYVhpQjIaEsZtHQKy", "IOBAEIbBnjO", "MyHjLicHnzyrvRxvtw", "WYt DPvcv", "c" }; string s("EMuBXhHEDpDOS"); 1 */