稀疏数组搜索。有个排好序的字符串数组,其中散布着一些空字符串,编写一种方法,找出给定字符串的位置。
示例1:
输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta" 输出:-1 说明: 不存在返回-1。
示例2:
输入:words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball" 输出:4
示例代码1:
class Solution(object):
def findString(self, words, s):
"""
:type words: List[str]
:type s: str
:rtype: int
"""
location = 0
for i in words:
if i == s:
return location
location += 1
return -1
示例代码2:
class Solution(object):
def findString(self, words, s):
"""
:type words: List[str]
:type s: str
:rtype: int
"""
try:
res = words.index(s)
except:
res = -1
return res
思路解析:
如果直接return words.index(s), s不存在时会出错
所以try...except,捕获到错误时,返回-1
示例代码3(二分查找):
class Solution(object):
def findString(self, words, s):
"""
:type words: List[str]
:type s: str
:rtype: int
"""
a, b = 0, len(words) - 1 # 左右指针
mid = (a+b) // 2 # 初始化
while a <= mid <= b:
if words[mid]: # 若words[mid]不为空字符串
if words[mid] > s: # 若words[mid]字符串比目标 s 大,则目标 s 一定在左半部分
b = mid - 1 # 则右指针减一
while a < b and words[b] == '': # 如果发现指针指向的字符串是空,就继续减一 直到找到非空字符串
b -= 1 # 注意条件中需要限制 右指针在左指针的右边
elif words[mid] < s:
a = mid + 1
while a < b and words[a] == '':
a += 1
else:
return mid
mid = (a+b) // 2
# 若words[mid]为空字符串,mid自增1。
else:
mid += 1
return -1