原文链接: https://leetcode-cn.com/problems/sparse-array-search-lcci

英文原文

Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string.

Example1:

 Input: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
 Output: -1
 Explanation: Return -1 if s is not in words.

Example2:

 Input: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
 Output: 4

Note:

1. 1 <= words.length <= 1000000

中文题目

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

示例1:

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

示例2:

 输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
 输出：4

提示:

1. words的长度在[1, 1000000]之间

通过代码

高赞题解

⏲阅读大约需要 3min

🔑解题思路

在二分上进行了变形，详解见注释

🐼代码部分

class Solution:
    def findString(self, words: List[str], s: str) -> int:
        left, right = 0, len(words) - 1
        while left <= right:
            mid = left + (right - left) // 2

            temp = mid  # 记录一下mid的位置，因为下面要移动mid来寻找非空串，如果查找失败需要用temp来恢复位置
            while words[mid] == '' and mid < right:  # 如果mid对应空串则向右寻找
                mid += 1
            if words[mid] == '':  
            # 该情况发生在mid走到了right-1的位置，如果right仍对应空，则说明temp右侧都是空，所以将右边界进行改变
                right = temp - 1
                continue
            if words[mid] == s:  # 该情况发生在mid在右移的过程中发现了非空串，则进行正常的二分查找
                return mid
            elif s < words[mid]:
                right = mid - 1
            else:
                left = mid + 1
        return -1

如果你喜欢这条题解的话，欢迎左下角点个赞👍👍👍

🎈在我的力扣主页@LotusPanda可以找到之前的文字题解和**视频题解(主页左侧有b站和油管链接)**，欢迎关注！

另，欢迎加入@fuxuemingzhu创建的每日一题打卡网站＆微信打卡群，传送门见主页左侧第3个链接(因官方禁止在题解区发布外部链接，就请大家去我的主页关注吧)

统计信息

通过次数	提交次数	AC比率
20525	36950	55.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言